1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Kadang-kadang, apabila membina sebuah
program, anda mungkin mahu untuk menggunakan

3
00:00:10,890 --> 00:00:13,190
struktur data yang dikenali sebagai kamus.

4
00:00:13,190 --> 00:00:17,960
Satu peta kamus kunci, yang
biasanya tali, untuk nilai-nilai, Ints,

5
00:00:17,960 --> 00:00:21,900
aksara, penunjuk kepada beberapa objek,
apa sahaja yang kita mahu.

6
00:00:21,900 --> 00:00:26,510
Ia hanya seperti kamus biasa
peta yang kata-kata melalui definisi.

7
00:00:26,510 --> 00:00:29,440
>> Kamus menyediakan kami dengan
keupayaan untuk menyimpan maklumat

8
00:00:29,440 --> 00:00:32,750
berkaitan dengan sesuatu
dan melihat ia kemudian.

9
00:00:32,750 --> 00:00:36,620
Jadi bagaimana kita sebenarnya melaksanakan
kamus, katakanlah, kod C yang kita boleh

10
00:00:36,620 --> 00:00:38,460
digunakan dalam salah satu program kita?

11
00:00:38,460 --> 00:00:41,790
Well, ada banyak cara yang
saya melaksanakannya kamus.

12
00:00:41,790 --> 00:00:45,930
>> Untuk satu, kita boleh menggunakan array yang kita
saiz semula secara dinamik atau kita boleh menggunakan

13
00:00:45,930 --> 00:00:49,150
senarai bersambung, jadual hash
atau pokok binari.

14
00:00:49,150 --> 00:00:52,250
Tetapi apa sahaja yang kita pilih, kita harus
prihatin terhadap kecekapan dan

15
00:00:52,250 --> 00:00:54,300
prestasi pelaksanaan.

16
00:00:54,300 --> 00:00:57,930
Kami perlu memikirkan algoritma yang digunakan
untuk memasukkan dan mencari item ke dalam

17
00:00:57,930 --> 00:00:59,120
struktur data kami.

18
00:00:59,120 --> 00:01:03,060
>> Buat masa ini, mari kita andaikan kita yang
mahu menggunakan tali sebagai kunci.

19
00:01:03,060 --> 00:01:07,290
Mari kita bercakap tentang satu kemungkinan,
struktur data dipanggil indone a.

20
00:01:07,290 --> 00:01:11,210
Jadi inilah perwakilan visual
daripada indone a.

21
00:01:11,210 --> 00:01:14,590
>> Seperti gambar mencadangkan, indone yang
adalah struktur data pokok yang

22
00:01:14,590 --> 00:01:16,050
nod dihubungkan bersama-sama.

23
00:01:16,050 --> 00:01:19,420
Kami melihat bahawa terdapat dengan jelas akar
nod dengan beberapa pautan untuk melanjutkan

24
00:01:19,420 --> 00:01:20,500
nod lain.

25
00:01:20,500 --> 00:01:23,040
Tetapi apakah setiap nod terdiri daripada?

26
00:01:23,040 --> 00:01:26,700
Jika kita menganggap bahawa kita menyimpan kunci
dengan hanya aksara abjad, dan

27
00:01:26,700 --> 00:01:30,150
kita tidak mengambil berat tentang permodalan,
inilah definisi nod yang

28
00:01:30,150 --> 00:01:31,100
memadai.

29
00:01:31,100 --> 00:01:34,130
>> Satu objek yang jenis adalah struct
nod mempunyai dua bahagian

30
00:01:34,130 --> 00:01:35,740
dipanggil data dan kanak-kanak.

31
00:01:35,740 --> 00:01:39,200
Kami telah meninggalkan sebahagian data sebagai komen
diganti oleh komponen

32
00:01:39,200 --> 00:01:43,190
pengisytiharan apabila nod struct adalah
yang diperbadankan di program C.

33
00:01:43,190 --> 00:01:47,040
Bahagian data nod mungkin
Nilai boolean untuk menunjukkan sama ada atau

34
00:01:47,040 --> 00:01:51,160
tidak nod mewakili siap
daripada kunci kamus atau ia mungkin

35
00:01:51,160 --> 00:01:54,240
string mewakili definisi
sebuah kata dalam kamus.

36
00:01:54,240 --> 00:01:58,870
>> Kami akan menggunakan muka senyum untuk menunjukkan
apabila data adalah di dalam nod.

37
00:01:58,870 --> 00:02:02,310
Terdapat 26 elemen dalam kami
anak-anak pelbagai, satu indeks

38
00:02:02,310 --> 00:02:03,690
setiap watak abjad.

39
00:02:03,690 --> 00:02:06,570
Kami akan melihat kepentingan
ini tidak lama lagi.

40
00:02:06,570 --> 00:02:10,759
>> Mari kita melihat dengan lebih dekat nod akar
dalam rajah kami, yang tidak mempunyai data

41
00:02:10,759 --> 00:02:14,740
yang dikaitkan dengannya, seperti yang ditunjukkan oleh
ketiadaan muka senyum dalam

42
00:02:14,740 --> 00:02:16,110
bahagian data.

43
00:02:16,110 --> 00:02:19,910
Anak panah bermula dari bahagian-bahagian
array kanak-kanak mewakili bukan nod-

44
00:02:19,910 --> 00:02:21,640
petunjuk untuk nod lain.

45
00:02:21,640 --> 00:02:25,500
Sebagai contoh, anak panah bermula dari
elemen kedua kanak-kanak

46
00:02:25,500 --> 00:02:28,400
mewakili huruf B yang
dalam kunci kamus.

47
00:02:28,400 --> 00:02:31,920
Dan dalam gambar rajah yang lebih besar
kita labelkan ia dengan B.

48
00:02:31,920 --> 00:02:35,810
>> Perhatikan bahawa dalam gambar rajah yang lebih besar, apabila kita
menarik penunjuk kepada nod yang lain, ia

49
00:02:35,810 --> 00:02:39,100
Tidak kira di mana mata panah
memenuhi nod yang lain.

50
00:02:39,100 --> 00:02:43,850
Indone sampel kamus kami mengandungi
dua perkataan, itu dan zum.

51
00:02:43,850 --> 00:02:47,040
Mari kita berjalan melalui satu contoh
melihat ke atas data untuk kunci.

52
00:02:47,040 --> 00:02:50,800
>> Katakan kita mahu mencari yang
nilai yang sepadan untuk mandi utama.

53
00:02:50,800 --> 00:02:53,610
Kami akan mula kelihatan kami sehingga
pada nod akar.

54
00:02:53,610 --> 00:02:57,870
Maka kita akan mengambil huruf pertama kami
utama, B, dan mencari yang sepadan

55
00:02:57,870 --> 00:03:00,020
melihat pada kanak-kanak pelbagai kami.

56
00:03:00,020 --> 00:03:04,490
Perhatikan bahawa ada hanya 26 tempat
dalam array, satu untuk setiap huruf

57
00:03:04,490 --> 00:03:05,330
abjad.

58
00:03:05,330 --> 00:03:08,800
Dan kami akan mempunyai tempat mewakili
huruf abjad teratur.

59
00:03:08,800 --> 00:03:13,960
>> Kita akan melihat indeks kedua kemudian,
indeks satu, untuk B. Secara umum, jika kita

60
00:03:13,960 --> 00:03:17,990
mempunyai beberapa abjad watak C kita
boleh menentukan tempat yang sama

61
00:03:17,990 --> 00:03:21,520
dalam pelbagai kanak-kanak yang menggunakan
pengiraan seperti ini.

62
00:03:21,520 --> 00:03:25,140
Kami boleh menggunakan kanak-kanak yang lebih besar
array jika kita mahu menawarkan kelihatan daripada

63
00:03:25,140 --> 00:03:28,380
kunci dengan pelbagai rangkaian aksara,
seperti keseluruhan

64
00:03:28,380 --> 00:03:29,880
Watak ASCII ditetapkan.

65
00:03:29,880 --> 00:03:32,630
>> Dalam kes ini, penunjuk
pada kanak-kanak pelbagai kami di

66
00:03:32,630 --> 00:03:34,320
indeks seseorang tidak batal.

67
00:03:34,320 --> 00:03:36,600
Oleh itu, kita akan terus mencari
sehingga mandi utama.

68
00:03:36,600 --> 00:03:40,130
Jika kita pernah dihadapi penunjuk null
di tempat yang betul dalam kanak-kanak

69
00:03:40,130 --> 00:03:43,230
array sementara kami dilalui nod,
maka kita akan katakan kita yang

70
00:03:43,230 --> 00:03:45,630
tidak dapat mencari apa-apa untuk utama yang.

71
00:03:45,630 --> 00:03:49,370
>> Sekarang, kita akan mengambil surat kedua
utama kami, A, dan terus mengikuti

72
00:03:49,370 --> 00:03:52,400
petunjuk dengan cara ini sehingga kita
sampai ke akhir utama kami.

73
00:03:52,400 --> 00:03:56,530
Jika kita sampai ke akhir kunci tanpa
memukul apa-apa buntu, petunjuk batal,

74
00:03:56,530 --> 00:03:59,730
seperti yang berlaku di sini, maka kita hanya
perlu menyemak satu lagi perkara.

75
00:03:59,730 --> 00:04:02,110
Adalah kunci ini sebenarnya
di dalam kamus?

76
00:04:02,110 --> 00:04:07,660
>> Jika demikian, kita perlu mencari nilai, baik yang
icon muka senyum dalam rajah kami di mana

77
00:04:07,660 --> 00:04:08,750
perkataan berakhir.

78
00:04:08,750 --> 00:04:12,270
Jika ada sesuatu yang lain disimpan dengan
data, maka kita boleh kembali.

79
00:04:12,270 --> 00:04:16,500
Sebagai contoh, zoo utama tidak dalam
kamus, walaupun kita boleh mempunyai

80
00:04:16,500 --> 00:04:19,810
sampai ke penghujung kunci ini tanpa
memukul penunjuk batal, sementara kami

81
00:04:19,810 --> 00:04:21,089
melelar melalui indone itu.

82
00:04:21,089 --> 00:04:25,436
>> Jika kita cuba untuk mencari mandi utama,
kedua untuk pelbagai indeks nod lepas,

83
00:04:25,436 --> 00:04:28,750
sepadan dengan huruf H, akan
memegang penunjuk null.

84
00:04:28,750 --> 00:04:31,120
Jadi mandi tidak ada di dalam kamus.

85
00:04:31,120 --> 00:04:34,800
Dan sebagainya indone adalah unik kerana kunci
tidak pernah jelas disimpan di dalam

86
00:04:34,800 --> 00:04:36,650
struktur data.

87
00:04:36,650 --> 00:04:38,810
Jadi bagaimana kita memasukkan sesuatu
ke indone satu?

88
00:04:38,810 --> 00:04:41,780
>> Mari kita memasukkan kunci
zoo ke dalam indone kami.

89
00:04:41,780 --> 00:04:46,120
Ingat bahawa muka senyum pada satu nod
boleh sesuai dalam kod untuk mudah

90
00:04:46,120 --> 00:04:50,170
Nilai boolean untuk menunjukkan zoo yang
di dalam kamus atau ia boleh

91
00:04:50,170 --> 00:04:53,710
sesuai dengan maklumat lanjut yang kita
ingin kaitkan dengan zoo utama,

92
00:04:53,710 --> 00:04:56,860
seperti definisi
perkataan atau sesuatu yang lain.

93
00:04:56,860 --> 00:05:00,350
Dalam beberapa cara, proses untuk memasukkan
sesuatu ke dalam indone yang adalah sama dengan

94
00:05:00,350 --> 00:05:02,060
melihat ke atas sesuatu di indone a.

95
00:05:02,060 --> 00:05:05,720
>> Kami akan bermula dengan nod akar sekali lagi,
petunjuk berikut bersamaan dengan

96
00:05:05,720 --> 00:05:07,990
huruf utama kami.

97
00:05:07,990 --> 00:05:11,310
Nasib baik, kami dapat mengikuti petunjuk
sepanjang jalan sehingga kita mencapai

98
00:05:11,310 --> 00:05:12,770
akhir kunci.

99
00:05:12,770 --> 00:05:16,480
Sejak zoo adalah awalan perkataan
zoom, yang merupakan ahli

100
00:05:16,480 --> 00:05:19,440
kamus, kita tidak perlu
memperuntukkan sebarang nod baru.

101
00:05:19,440 --> 00:05:23,140
>> Kita boleh mengubah nod untuk menandakan bahawa
jalan watak-watak utama untuk

102
00:05:23,140 --> 00:05:25,360
ia merupakan penting dalam kamus kami.

103
00:05:25,360 --> 00:05:28,630
Sekarang, mari kita cuba memasukkan
MANDI utama ke indone itu.

104
00:05:28,630 --> 00:05:32,260
Kita bermula pada nod akar
dan ikuti petunjuk lagi.

105
00:05:32,260 --> 00:05:35,620
Tetapi dalam keadaan ini, kita mencapai mati seorang
berakhir sebelum kita dapat sampai ke

106
00:05:35,620 --> 00:05:36,940
akhir kunci.

107
00:05:36,940 --> 00:05:40,980
Sekarang, kita perlu memperuntukkan beberapa baru
nod perlu memperuntukkan yang baru

108
00:05:40,980 --> 00:05:43,660
nod bagi setiap baki
surat utama kami.

109
00:05:43,660 --> 00:05:46,740
>> Dalam kes ini, kita hanya perlu
untuk memperuntukkan satu nod baru.

110
00:05:46,740 --> 00:05:50,590
Maka kita perlu membuat indeks H
rujukan nod baru ini.

111
00:05:50,590 --> 00:05:54,070
Sekali lagi, kami boleh mengubah suai nod untuk
menunjukkan bahawa laluan aksara

112
00:05:54,070 --> 00:05:57,120
yang membawa kepada ia merupakan
utama dalam kamus kami.

113
00:05:57,120 --> 00:06:00,730
Mari kita sebab tentang asimptot
kerumitan prosedur kami bagi

114
00:06:00,730 --> 00:06:02,110
dua operasi.

115
00:06:02,110 --> 00:06:06,420
>> Kami melihat bahawa kedua-dua kes bilangan
daripada langkah algoritma kami mengambil masa telah

116
00:06:06,420 --> 00:06:09,470
berkadar dengan bilangan
huruf dalam kata kunci.

117
00:06:09,470 --> 00:06:10,220
Betul.

118
00:06:10,220 --> 00:06:13,470
Apabila anda mahu mencari perkataan dalam
indone anda hanya perlu melelar melalui

119
00:06:13,470 --> 00:06:17,100
huruf satu demi satu sehingga anda sama ada
sampai ke akhir perkataan atau

120
00:06:17,100 --> 00:06:19,060
menemui jalan buntu di indone itu.

121
00:06:19,060 --> 00:06:22,470
>> Dan apabila anda ingin memasukkan kunci yang
pasangan nilai ke indone yang menggunakan

122
00:06:22,470 --> 00:06:26,250
prosedur yang kita dibincangkan, kes yang paling teruk
akan anda memperuntukkan nod baru

123
00:06:26,250 --> 00:06:27,550
untuk setiap huruf.

124
00:06:27,550 --> 00:06:31,290
Dan kita akan menganggap peruntukan yang
adalah operasi masa yang sama.

125
00:06:31,290 --> 00:06:35,850
Jadi, jika kita menganggap bahawa panjang utama adalah
disempadani oleh yang tetap tetap, kedua-dua

126
00:06:35,850 --> 00:06:39,400
kemasukan dan mencari adalah malar
operasi masa untuk indone a.

127
00:06:39,400 --> 00:06:42,930
>> Jika kita tidak membuat andaian ini yang
panjang utama disempadani oleh tetap

128
00:06:42,930 --> 00:06:46,650
berterusan, maka lampiran dan mencari,
dalam kes paling teruk, adalah linear dalam

129
00:06:46,650 --> 00:06:48,240
Panjang kunci.

130
00:06:48,240 --> 00:06:51,800
Perhatikan bahawa bilangan item yang disimpan
di indone tidak menjejaskan rupa sehingga

131
00:06:51,800 --> 00:06:52,820
atau masa kemasukan.

132
00:06:52,820 --> 00:06:55,360
Ia hanya kesan daripada
Panjang kunci.

133
00:06:55,360 --> 00:06:59,300
>> Sebaliknya, menambah catatan untuk, katakan,
jadual hash cenderung untuk membuat

134
00:06:59,300 --> 00:07:01,250
masa depan mencari lebih perlahan.

135
00:07:01,250 --> 00:07:04,520
Manakala ini mungkin berbunyi menarik pada mulanya,
kita harus ingat bahawa

136
00:07:04,520 --> 00:07:08,740
kerumitan asimptot baik tidak
bermakna dalam amalan data yang

137
00:07:08,740 --> 00:07:11,410
struktur semestinya
luar teguran.

138
00:07:11,410 --> 00:07:15,860
Kami juga perlu mengambil kira bahawa untuk menyimpan
perkataan dalam indone kita perlukan, yang paling teruk

139
00:07:15,860 --> 00:07:19,700
kes, beberapa nod berkadar
dengan panjang perkataan itu sendiri.

140
00:07:19,700 --> 00:07:21,880
>> Percubaan yang cenderung untuk menggunakan banyak ruang.

141
00:07:21,880 --> 00:07:25,620
Itu berbeza dengan jadual hash,
di mana kita hanya perlu satu nod baru untuk

142
00:07:25,620 --> 00:07:27,940
menyimpan beberapa pasangan nilai utama.

143
00:07:27,940 --> 00:07:31,370
Kini, sekali lagi dalam teori, ruang yang besar
penggunaan tidak kelihatan seperti yang besar

144
00:07:31,370 --> 00:07:34,620
berurusan, terutamanya yang moden
komputer mempunyai gigabait dan

145
00:07:34,620 --> 00:07:36,180
gigabait memori.

146
00:07:36,180 --> 00:07:39,200
Tetapi ternyata bahawa kita masih mempunyai
bimbang tentang penggunaan memori dan

147
00:07:39,200 --> 00:07:42,540
organisasi demi
Prestasi, kerana komputer moden

148
00:07:42,540 --> 00:07:46,960
mempunyai mekanisme di tempat di bawah
hud untuk mempercepatkan akses ingatan.

149
00:07:46,960 --> 00:07:51,180
>> Tetapi mekanisme ini berfungsi terbaik apabila
Akses tak memori dibuat padat

150
00:07:51,180 --> 00:07:52,810
kawasan atau kawasan-kawasan.

151
00:07:52,810 --> 00:07:55,910
Dan nod indone yang boleh tinggal
mana-mana sahaja dalam timbunan itu.

152
00:07:55,910 --> 00:07:58,390
Tetapi ini adalah keseimbangan
bahawa kita perlu mengambil kira.

153
00:07:58,390 --> 00:08:01,440
>> Ingat bahawa, apabila memilih data yang
struktur untuk tugas tertentu, kita

154
00:08:01,440 --> 00:08:04,420
perlu memikirkan apa jenis
operasi struktur data yang perlu

155
00:08:04,420 --> 00:08:07,140
sokongan dan berapa banyak prestasi
setiap mereka

156
00:08:07,140 --> 00:08:09,080
perkara-perkara operasi kepada kami.

157
00:08:09,080 --> 00:08:11,300
Operasi-operasi ini mungkin juga
melampaui hanya

158
00:08:11,300 --> 00:08:13,430
lihat asas dan sisipan.

159
00:08:13,430 --> 00:08:17,010
Katakan kita mahu melaksanakan jenis yang
fungsi auto-lengkap, banyak

160
00:08:17,010 --> 00:08:18,890
seperti enjin carian Google tidak.

161
00:08:18,890 --> 00:08:22,210
Iaitu, kembali semua kunci dan
nilai-nilai yang berpotensi

162
00:08:22,210 --> 00:08:24,130
mempunyai awalan yang diberikan.

163
00:08:24,130 --> 00:08:27,050
>> Indone adalah unik berguna
untuk operasi ini.

164
00:08:27,050 --> 00:08:29,890
Ia mudah untuk melelar melalui
yang indone bagi setiap watak

165
00:08:29,890 --> 00:08:30,950
awalan.

166
00:08:30,950 --> 00:08:33,559
Sama seperti operasi mencari,
kita boleh mengikuti petunjuk

167
00:08:33,559 --> 00:08:35,400
watak oleh watak.

168
00:08:35,400 --> 00:08:38,659
Kemudian, apabila kita tiba di akhir
awalan, kita boleh melelar melalui

169
00:08:38,659 --> 00:08:42,049
baki bahan struktur data
sejak mana-mana kekunci di luar

170
00:08:42,049 --> 00:08:43,980
ketika ini mempunyai awalan.

171
00:08:43,980 --> 00:08:47,670
>> Ia juga mudah untuk mendapatkan penyenaraian ini
mengikut abjad sejak

172
00:08:47,670 --> 00:08:50,970
unsur-unsur pelbagai kanak-kanak yang
yang diperintahkan mengikut abjad.

173
00:08:50,970 --> 00:08:54,420
Jadi mudah-mudahan anda akan mempertimbangkan
pemberian cuba cuba.

174
00:08:54,420 --> 00:08:56,085
Saya Kevin Schmid, dan ini adalah CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, ini adalah permulaan
penurunan.

177
00:09:00,790 --> 00:09:01,350
Saya minta maaf.

178
00:09:01,350 --> 00:09:01,870
Maaf.

179
00:09:01,870 --> 00:09:02,480
Maaf.

180
00:09:02,480 --> 00:09:03,130
Maaf.

181
00:09:03,130 --> 00:09:03,950
>> Menyerang empat.

182
00:09:03,950 --> 00:09:04,360
Aku keluar.

183
00:09:04,360 --> 00:09:05,280
Maaf.

184
00:09:05,280 --> 00:09:06,500
Maaf.

185
00:09:06,500 --> 00:09:07,490
Maaf.

186
00:09:07,490 --> 00:09:12,352
Maaf untuk membuat orang yang
telah menyunting laman ini pergi gila.

187
00:09:12,352 --> 00:09:13,280
>> Maaf.

188
00:09:13,280 --> 00:09:13,880
Maaf.

189
00:09:13,880 --> 00:09:15,080
Maaf.

190
00:09:15,080 --> 00:09:15,680
Maaf.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1 Syabas.

192
00:09:16,280 --> 00:09:17,530
Yang benar-benar dilakukan dengan baik.

193
00:09:17,530 --> 00:09:18,430