1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Jadi di CS50, kita telah membahas
banyak struktur data yang berbeda,

3
00:00:08,300 --> 00:00:09,180
benar?

4
00:00:09,180 --> 00:00:11,420
Kami telah melihat array, dan terkait
daftar, dan tabel hash,

5
00:00:11,420 --> 00:00:15,210
dan mencoba, tumpukan dan antrian.

6
00:00:15,210 --> 00:00:17,579
Kami juga akan belajar sedikit
tentang pohon dan tumpukan,

7
00:00:17,579 --> 00:00:20,120
tapi benar-benar ini semua hanya berakhir
sampai menjadi variasi pada tema.

8
00:00:20,120 --> 00:00:22,840
Benar-benar ada ini
jenis empat ide dasar

9
00:00:22,840 --> 00:00:25,190
bahwa segala sesuatu yang lain dapat mendidih ke.

10
00:00:25,190 --> 00:00:28,150
Array, daftar link,
tabel hash, dan mencoba.

11
00:00:28,150 --> 00:00:30,720
Dan seperti saya katakan, ada
variasi pada mereka,

12
00:00:30,720 --> 00:00:32,720
tapi ini cukup
banyak terjadi untuk meringkas

13
00:00:32,720 --> 00:00:38,140
segala sesuatu yang kita akan berbicara
tentang di kelas ini dalam hal C.

14
00:00:38,140 --> 00:00:40,140
>> Tapi bagaimana ini semua ukuran, kan?

15
00:00:40,140 --> 00:00:44,265
Kami telah berbicara tentang pro dan kontra
masing-masing dalam video terpisah pada mereka,

16
00:00:44,265 --> 00:00:46,390
tapi ada banyak nomor
mendapatkan dilemparkan sekitar.

17
00:00:46,390 --> 00:00:48,723
Ada banyak umum
pikiran mendapatkan dilemparkan sekitar.

18
00:00:48,723 --> 00:00:51,950
Mari kita coba dan mengkonsolidasikan
menjadi hanya satu tempat.

19
00:00:51,950 --> 00:00:55,507
Mari kita menimbang pro terhadap
kontra, dan mempertimbangkan

20
00:00:55,507 --> 00:00:57,340
yang struktur data
mungkin data yang benar

21
00:00:57,340 --> 00:01:01,440
struktur untuk situasi khusus Anda,
apa pun jenis data yang Anda menyimpan.

22
00:01:01,440 --> 00:01:06,625
Anda tidak perlu selalu perlu
menggunakan penyisipan super cepat, penghapusan,

23
00:01:06,625 --> 00:01:10,761
dan pencarian dari trie jika Anda benar-benar
tidak peduli tentang memasukkan dan menghapus

24
00:01:10,761 --> 00:01:11,260
terlalu banyak.

25
00:01:11,260 --> 00:01:13,968
Jika Anda hanya perlu cepat acak
Akses, mungkin array lebih baik.

26
00:01:13,968 --> 00:01:15,340
Jadi mari kita menyaring itu.

27
00:01:15,340 --> 00:01:18,530
Mari kita bicara tentang masing-masing empat
jenis utama dari struktur data

28
00:01:18,530 --> 00:01:21,720
yang kita bicarakan, dan
hanya melihat ketika mereka mungkin baik,

29
00:01:21,720 --> 00:01:23,340
dan ketika mereka mungkin tidak begitu baik.

30
00:01:23,340 --> 00:01:24,610
Jadi mari kita mulai dengan array.

31
00:01:24,610 --> 00:01:27,300
Jadi penyisipan, itu semacam buruk.

32
00:01:27,300 --> 00:01:31,350
>> Penyisipan pada akhir array adalah OK,
jika kita sedang membangun sebuah array seperti yang kita pergi.

33
00:01:31,350 --> 00:01:33,570
Tetapi jika kita harus memasukkan
unsur ke tengah,

34
00:01:33,570 --> 00:01:35,550
berpikir kembali ke penyisipan
macam, ada banyak

35
00:01:35,550 --> 00:01:37,510
pergeseran untuk menyesuaikan elemen di sana.

36
00:01:37,510 --> 00:01:41,170
Dan jadi jika kita akan memasukkan
mana saja tapi akhir array,

37
00:01:41,170 --> 00:01:43,590
itu mungkin tidak begitu besar.

38
00:01:43,590 --> 00:01:46,710
>> Demikian pula, penghapusan, kecuali kami
menghapus dari akhir array,

39
00:01:46,710 --> 00:01:49,810
mungkin juga tidak begitu besar jika
kita tidak ingin meninggalkan celah kosong,

40
00:01:49,810 --> 00:01:50,790
yang biasanya kita lakukan tidak.

41
00:01:50,790 --> 00:01:54,700
Kami ingin menghapus elemen, dan
maka semacam membuatnya snug lagi.

42
00:01:54,700 --> 00:01:57,670
Dan menghapus elemen dari
array, juga tidak begitu besar.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, meskipun, adalah besar.

44
00:01:58,820 --> 00:02:00,920
Kami memiliki akses random,
konstan lookup waktu.

45
00:02:00,920 --> 00:02:03,800
Kami hanya mengatakan tujuh, dan kami pergi
array relokasi tujuh.

46
00:02:03,800 --> 00:02:05,907
Kita mengatakan 20, dengan pergi ke
Array relokasi 20.

47
00:02:05,907 --> 00:02:07,240
Kami tidak perlu iterate seluruh.

48
00:02:07,240 --> 00:02:08,630
Itu cukup bagus.

49
00:02:08,630 --> 00:02:11,020
>> Array juga relatif mudah untuk menyortir.

50
00:02:11,020 --> 00:02:14,040
Setiap kali kita berbicara tentang pemilahan sebuah
algoritma, seperti pemilihan semacam,

51
00:02:14,040 --> 00:02:18,820
insertion sort, bubble sort, menggabungkan
semacam, kami selalu menggunakan array untuk melakukannya,

52
00:02:18,820 --> 00:02:21,860
karena array cukup mudah untuk
semacam, relatif terhadap struktur data

53
00:02:21,860 --> 00:02:22,970
kita lihat sejauh ini.

54
00:02:22,970 --> 00:02:24,320
>> Mereka juga relatif kecil.

55
00:02:24,320 --> 00:02:25,695
Tidak ada banyak ruang ekstra.

56
00:02:25,695 --> 00:02:29,210
Anda hanya menyisihkan persis sebanyak
yang Anda butuhkan untuk menyimpan data Anda,

57
00:02:29,210 --> 00:02:30,320
dan itu cukup banyak itu.

58
00:02:30,320 --> 00:02:33,180
Jadi mereka cukup kecil
dan efisien dengan cara itu.

59
00:02:33,180 --> 00:02:36,000
Tapi downside lain, meskipun,
adalah bahwa mereka tetap dalam ukuran.

60
00:02:36,000 --> 00:02:38,630
Kita harus menyatakan persis bagaimana
besar kita ingin array kita menjadi,

61
00:02:38,630 --> 00:02:39,940
dan kami hanya punya satu kesempatan itu.

62
00:02:39,940 --> 00:02:41,280
Kita tidak dapat tumbuh dan menyusut.

63
00:02:41,280 --> 00:02:44,582
>> Jika kita perlu tumbuh atau menyusut itu, kami
perlu mendeklarasikan array yang sama sekali baru,

64
00:02:44,582 --> 00:02:47,750
menyalin semua elemen dari
pertama array ke dalam array kedua.

65
00:02:47,750 --> 00:02:51,410
Dan jika kita salah perhitungan yang
waktu, kita perlu melakukannya lagi.

66
00:02:51,410 --> 00:02:52,760
Tidak begitu besar.

67
00:02:52,760 --> 00:02:58,750
Jadi array tidak memberikan fleksibilitas
untuk memiliki nomor variabel elemen.

68
00:02:58,750 --> 00:03:01,320
>> Dengan linked list,
penyisipan cukup mudah.

69
00:03:01,320 --> 00:03:03,290
Kami hanya taktik ke depan.

70
00:03:03,290 --> 00:03:04,892
Penghapusan ini juga cukup mudah.

71
00:03:04,892 --> 00:03:06,100
Kita harus menemukan unsur-unsur.

72
00:03:06,100 --> 00:03:07,270
Yang melibatkan beberapa pencarian.

73
00:03:07,270 --> 00:03:10,270
>> Tetapi sekali Anda telah menemukan elemen
Anda sedang mencari, semua yang perlu Anda lakukan

74
00:03:10,270 --> 00:03:12,830
adalah mengubah pointer,
mungkin dua jika Anda memiliki

75
00:03:12,830 --> 00:03:15,151
a terkait list-- sebuah ganda
linked list, rather--

76
00:03:15,151 --> 00:03:16,650
dan kemudian Anda hanya dapat membebaskan node.

77
00:03:16,650 --> 00:03:18,399
Anda tidak perlu menggeser
segala sesuatu di sekitar.

78
00:03:18,399 --> 00:03:22,090
Anda hanya mengubah dua pointer,
jadi itu cukup cepat.

79
00:03:22,090 --> 00:03:23,470
>> Lookup buruk sekalipun, kan?

80
00:03:23,470 --> 00:03:26,280
Agar kita untuk menemukan
elemen dalam linked list,

81
00:03:26,280 --> 00:03:29,154
apakah tunggal atau ganda terkait,
kita harus linier mencari itu.

82
00:03:29,154 --> 00:03:32,320
Kita harus mulai dari awal dan
bergerak akhirnya, atau mulai bergerak akhir

83
00:03:32,320 --> 00:03:33,860
ke awal.

84
00:03:33,860 --> 00:03:35,474
Kami tidak memiliki akses acak lagi.

85
00:03:35,474 --> 00:03:37,265
Jadi jika kita melakukan
banyak pencarian, mungkin

86
00:03:37,265 --> 00:03:39,830
linked list tidak
begitu baik bagi kita.

87
00:03:39,830 --> 00:03:43,750
>> Mereka juga benar-benar
sulit untuk memilah, kan?

88
00:03:43,750 --> 00:03:45,666
Satu-satunya cara Anda bisa
benar-benar memilah linked list

89
00:03:45,666 --> 00:03:47,870
adalah untuk mengatasinya seperti yang Anda membangun itu.

90
00:03:47,870 --> 00:03:50,497
Tetapi jika Anda mengatasinya seperti yang Anda
membangun itu, Anda tidak lagi

91
00:03:50,497 --> 00:03:51,830
membuat sisipan cepat lagi.

92
00:03:51,830 --> 00:03:53,746
Anda tidak hanya memaku
hal ke depan.

93
00:03:53,746 --> 00:03:55,710
Anda harus menemukan
tempat yang tepat untuk meletakkannya,

94
00:03:55,710 --> 00:03:57,820
dan kemudian penyisipan Anda
menjadi hanya tentang buruknya

95
00:03:57,820 --> 00:03:59,390
sebagai memasukkan ke dalam sebuah array.

96
00:03:59,390 --> 00:04:03,130
Jadi daftar terkait tidak
begitu besar untuk menyortir data.

97
00:04:03,130 --> 00:04:05,830
>> Mereka juga cukup kecil, ukuran-bijaksana.

98
00:04:05,830 --> 00:04:08,496
Ganda terkait daftar sedikit
lebih besar dari daftar tunggal terkait,

99
00:04:08,496 --> 00:04:10,620
yang sedikit lebih besar
dari array, tapi tidak

100
00:04:10,620 --> 00:04:13,330
sejumlah besar ruang kosong.

101
00:04:13,330 --> 00:04:18,730
Jadi jika ruang adalah pada premium, tapi
bukan premium benar-benar intens,

102
00:04:18,730 --> 00:04:22,180
ini mungkin menjadi cara yang tepat untuk pergi.

103
00:04:22,180 --> 00:04:23,330
>> Tabel hash.

104
00:04:23,330 --> 00:04:25,850
Penyisipan ke dalam tabel hash
cukup mudah.

105
00:04:25,850 --> 00:04:26,980
Ini adalah proses dua langkah.

106
00:04:26,980 --> 00:04:30,700
Pertama kita perlu menjalankan data kami melalui
fungsi hash untuk mendapatkan kode hash,

107
00:04:30,700 --> 00:04:37,550
dan kemudian kita memasukkan unsur ke dalam
tabel hash pada lokasi kode hash.

108
00:04:37,550 --> 00:04:40,879
>> Penghapusan, mirip dengan linked list,
mudah setelah Anda menemukan elemen.

109
00:04:40,879 --> 00:04:43,170
Anda harus menemukan pertama,
tapi kemudian ketika Anda menghapusnya,

110
00:04:43,170 --> 00:04:45,128
Anda hanya perlu untuk bertukar
beberapa pointer,

111
00:04:45,128 --> 00:04:47,250
jika Anda menggunakan chaining terpisah.

112
00:04:47,250 --> 00:04:49,942
Jika Anda menggunakan menyelidik,
atau jika Anda tidak

113
00:04:49,942 --> 00:04:51,650
menggunakan chaining sama sekali
dalam tabel hash Anda,

114
00:04:51,650 --> 00:04:53,040
penghapusan sebenarnya sangat mudah.

115
00:04:53,040 --> 00:04:57,134
Yang perlu Anda lakukan adalah hash
data, dan kemudian pergi ke lokasi tersebut.

116
00:04:57,134 --> 00:04:58,925
Dan dengan asumsi Anda tidak
memiliki tabrakan,

117
00:04:58,925 --> 00:05:01,650
Anda akan dapat menghapus sangat cepat.

118
00:05:01,650 --> 00:05:04,930
>> Sekarang, lookup mana hal-hal
mendapatkan sedikit lebih rumit.

119
00:05:04,930 --> 00:05:06,910
Ini rata-rata yang lebih baik
dari daftar terkait.

120
00:05:06,910 --> 00:05:09,560
Jika Anda menggunakan chaining,
Anda masih memiliki daftar link,

121
00:05:09,560 --> 00:05:13,170
yang berarti Anda masih memiliki
pencarian merugikan linked list.

122
00:05:13,170 --> 00:05:18,390
Tetapi karena Anda mengambil terkait Anda
daftar dan memisahkan lebih dari 100 atau 1000

123
00:05:18,390 --> 00:05:25,380
atau n elemen dalam tabel hash Anda, Anda
daftar terkait semua adalah satu-n ukuran.

124
00:05:25,380 --> 00:05:27,650
Mereka semua secara substansial lebih kecil.

125
00:05:27,650 --> 00:05:32,080
Anda telah n terkait daftar bukannya
dari salah satu daftar link dari ukuran n.

126
00:05:32,080 --> 00:05:34,960
>> Dan begitu nyata-dunia ini konstan
faktor, yang we umumnya

127
00:05:34,960 --> 00:05:39,730
tidak berbicara tentang kompleksitas waktu,
tidak benar-benar membuat perbedaan di sini.

128
00:05:39,730 --> 00:05:43,020
Jadi lookup masih linear
pencarian jika Anda menggunakan chaining,

129
00:05:43,020 --> 00:05:46,780
tapi panjang daftar
Anda mencari melalui

130
00:05:46,780 --> 00:05:50,080
sangat, sangat singkat dengan perbandingan.

131
00:05:50,080 --> 00:05:52,995
Sekali lagi, jika Anda adalah pemilahan
tujuan di sini, tabel hash ini

132
00:05:52,995 --> 00:05:54,370
mungkin bukan cara yang tepat untuk pergi.

133
00:05:54,370 --> 00:05:56,830
Hanya menggunakan sebuah array jika pemilahan
benar-benar penting bagi Anda.

134
00:05:56,830 --> 00:05:58,590
>> Dan mereka dapat menjalankan keseluruhan dari ukuran.

135
00:05:58,590 --> 00:06:01,640
Sulit untuk mengatakan apakah
tabel hash kecil atau besar,

136
00:06:01,640 --> 00:06:04,110
karena itu benar-benar tergantung pada
seberapa besar tabel hash Anda.

137
00:06:04,110 --> 00:06:07,340
Jika Anda hanya akan menyimpan
lima unsur dalam tabel hash Anda,

138
00:06:07,340 --> 00:06:10,620
dan Anda memiliki tabel hash
dengan 10.000 elemen di dalamnya,

139
00:06:10,620 --> 00:06:12,614
Anda mungkin membuang-buang banyak ruang.

140
00:06:12,614 --> 00:06:15,030
Kontras yang Anda dapat juga
memiliki tabel hash sangat kompak,

141
00:06:15,030 --> 00:06:18,720
tapi tabel hash Anda lebih kecil mendapat,
yang masing-masing terhubung daftar lagi

142
00:06:18,720 --> 00:06:19,220
mendapat.

143
00:06:19,220 --> 00:06:22,607
Dan sehingga benar-benar ada cara untuk mendefinisikan
persis ukuran tabel hash,

144
00:06:22,607 --> 00:06:24,440
tapi mungkin aman
mengatakan itu umumnya

145
00:06:24,440 --> 00:06:27,990
akan menjadi lebih besar dari yang terkait
Daftar menyimpan data yang sama,

146
00:06:27,990 --> 00:06:30,400
tetapi lebih kecil dari trie.

147
00:06:30,400 --> 00:06:32,720
>> Dan mencoba adalah keempat
struktur ini

148
00:06:32,720 --> 00:06:34,070
bahwa kita telah berbicara tentang.

149
00:06:34,070 --> 00:06:36,450
Memasukkan ke dalam trie adalah kompleks.

150
00:06:36,450 --> 00:06:38,400
Ada banyak dinamis
alokasi memori,

151
00:06:38,400 --> 00:06:40,780
terutama di awal,
karena Anda mulai membangun.

152
00:06:40,780 --> 00:06:43,700
Tapi itu waktu yang konstan.

153
00:06:43,700 --> 00:06:47,690
Ini hanya unsur manusia
di sini yang membuatnya rumit.

154
00:06:47,690 --> 00:06:53,250
Harus menghadapi pointer null, malloc
ruang, pergi ke sana, ruang mungkin malloc

155
00:06:53,250 --> 00:06:54,490
dari sana lagi.

156
00:06:54,490 --> 00:06:58,880
Semacam faktor intimidasi dari
pointer di alokasi memori dinamis

157
00:06:58,880 --> 00:07:00,130
adalah rintangan untuk menghapus.

158
00:07:00,130 --> 00:07:04,550
Tapi setelah Anda sudah membersihkan itu, penyisipan
sebenarnya berasal cukup sederhana,

159
00:07:04,550 --> 00:07:06,810
dan tentu waktu yang konstan.

160
00:07:06,810 --> 00:07:07,680
>> Penghapusan mudah.

161
00:07:07,680 --> 00:07:11,330
Yang perlu Anda lakukan adalah menavigasi turun
beberapa petunjuk dan bebas node,

162
00:07:11,330 --> 00:07:12,420
jadi itu cukup bagus.

163
00:07:12,420 --> 00:07:13,930
Lookup juga cukup cepat.

164
00:07:13,930 --> 00:07:16,780
Itu hanya berdasarkan
panjang data Anda.

165
00:07:16,780 --> 00:07:19,924
Jadi, jika semua data Anda
lima senar karakter,

166
00:07:19,924 --> 00:07:22,590
misalnya, Anda menyimpan lima
karakter string dalam trie Anda,

167
00:07:22,590 --> 00:07:25,439
hanya membutuhkan waktu lima langkah untuk
menemukan apa yang Anda cari.

168
00:07:25,439 --> 00:07:28,480
Lima hanyalah faktor konstan, sehingga
lagi, penyisipan, penghapusan, dan lookup

169
00:07:28,480 --> 00:07:31,670
di sini adalah semua waktu yang konstan, secara efektif.

170
00:07:31,670 --> 00:07:34,880
>> Hal lain adalah bahwa trie Anda
sebenarnya jenis yang sudah disortir, kan?

171
00:07:34,880 --> 00:07:36,800
Berdasarkan bagaimana kami
memasukkan unsur-unsur,

172
00:07:36,800 --> 00:07:40,060
dengan pergi huruf demi huruf dari
kunci, atau digit dengan digit kunci,

173
00:07:40,060 --> 00:07:45,084
biasanya, trie Anda akhirnya menjadi
jenis diurutkan sebagai Anda membangun itu.

174
00:07:45,084 --> 00:07:47,250
Itu tidak benar-benar membuat
akal untuk berpikir tentang pemilahan

175
00:07:47,250 --> 00:07:49,874
dengan cara yang sama kita berpikir tentang
dengan array, atau daftar link,

176
00:07:49,874 --> 00:07:51,070
atau tabel hash.

177
00:07:51,070 --> 00:07:54,780
Tapi dalam beberapa hal, Anda
trie diurutkan sebagai Anda pergi.

178
00:07:54,780 --> 00:07:58,630
>> Sisi negatifnya, tentu saja, adalah bahwa
trie cepat menjadi besar.

179
00:07:58,630 --> 00:08:02,970
Dari setiap titik persimpangan, Anda mungkin
have-- jika kunci Anda terdiri dari digit,

180
00:08:02,970 --> 00:08:04,880
Anda memiliki 10 lainnya
tempat Anda bisa pergi, yang

181
00:08:04,880 --> 00:08:07,490
berarti bahwa setiap simpul
berisi informasi

182
00:08:07,490 --> 00:08:11,440
tentang data yang Anda ingin menyimpan
pada saat itu node, ditambah 10 pointer.

183
00:08:11,440 --> 00:08:14,430
Yang, pada CS50 IDE, adalah 80 byte.

184
00:08:14,430 --> 00:08:17,220
Jadi itu setidaknya 80 byte untuk
setiap node yang Anda buat,

185
00:08:17,220 --> 00:08:19,240
dan itu bahkan tidak menghitung data.

186
00:08:19,240 --> 00:08:24,950
Dan jika node Anda
huruf bukan angka,

187
00:08:24,950 --> 00:08:27,825
sekarang Anda memiliki 26 pointer
dari setiap lokasi.

188
00:08:27,825 --> 00:08:32,007
Dan 26 kali 8 mungkin 200
byte, atau sesuatu seperti itu.

189
00:08:32,007 --> 00:08:33,840
Dan Anda memiliki modal
dan lowercase-- Anda dapat

190
00:08:33,840 --> 00:08:35,381
melihat di mana aku akan dengan ini, kan?

191
00:08:35,381 --> 00:08:37,500
Node Anda bisa benar-benar
besar, dan trie

192
00:08:37,500 --> 00:08:40,470
itu sendiri, secara keseluruhan, bisa
mendapatkan benar-benar besar, juga.

193
00:08:40,470 --> 00:08:42,630
Jadi jika ruang adalah pada tinggi
premi pada sistem Anda,

194
00:08:42,630 --> 00:08:45,830
trie mungkin bukan cara yang tepat untuk
pergi, meskipun manfaat lainnya

195
00:08:45,830 --> 00:08:47,780
ikut bermain.

196
00:08:47,780 --> 00:08:48,710
Aku Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Ini adalah CS50.

198
00:08:50,740 --> 00:08:52,316