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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Jadi dalam CS50, kami telah dilindungi
banyak struktur data yang berbeza,

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

4
00:00:09,180 --> 00:00:11,420
Kami telah melihat array, dan dikaitkan
senarai dan jadual hash,

5
00:00:11,420 --> 00:00:15,210
dan percubaan, susunan dan beratur.

6
00:00:15,210 --> 00:00:17,579
Kami juga akan belajar sedikit
mengenai pokok dan timbunan,

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

8
00:00:20,120 --> 00:00:22,840
Ada benar-benar ini
jenis empat idea-idea asas

9
00:00:22,840 --> 00:00:25,190
semua yang lain boleh mendidih ke.

10
00:00:25,190 --> 00:00:28,150
Tatasusunan, senarai berkaitan,
jadual hash, dan cuba.

11
00:00:28,150 --> 00:00:30,720
Dan seperti yang saya katakan, terdapat
variasi kepada mereka,

12
00:00:30,720 --> 00:00:32,720
tetapi ini adalah cukup
banyak berlaku untuk meringkaskan

13
00:00:32,720 --> 00:00:38,140
semua yang kita akan bercakap
kira-kira dalam kelas ini dari segi C.

14
00:00:38,140 --> 00:00:40,140
>> Tetapi bagaimana ini semua langkah, bukan?

15
00:00:40,140 --> 00:00:44,265
Kami telah berbincang mengenai kebaikan dan keburukan
setiap dalam video berasingan ke atas mereka,

16
00:00:44,265 --> 00:00:46,390
tetapi ada banyak nombor
mendapat dibuang di sekitar.

17
00:00:46,390 --> 00:00:48,723
Ada banyak umum
Pemikiran mendapat dibuang di sekitar.

18
00:00:48,723 --> 00:00:51,950
Mari kita cuba dan menyatukan
ia ke dalam hanya satu tempat.

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

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

21
00:00:57,340 --> 00:01:01,440
struktur bagi keadaan tertentu anda,
apa jua jenis data anda menyimpan.

22
00:01:01,440 --> 00:01:06,625
Anda tidak semestinya sentiasa perlu
menggunakan pemasukan super cepat, penghapusan,

23
00:01:06,625 --> 00:01:10,761
dan lookup daripada indone jika anda benar-benar
tidak mengambil berat tentang memasukkan dan memotong

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

25
00:01:11,260 --> 00:01:13,968
Jika anda perlukan hanya cepat rawak
akses, mungkin array adalah lebih baik.

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

27
00:01:15,340 --> 00:01:18,530
Mari kita bercakap tentang setiap satu daripada empat
jenis utama struktur data

28
00:01:18,530 --> 00:01:21,720
bahawa kita telah bercakap tentang, dan
hanya melihat ketika mereka mungkin baik,

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

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

31
00:01:24,610 --> 00:01:27,300
Jadi kemasukan, itu jenis yang tidak baik.

32
00:01:27,300 --> 00:01:31,350
>> Insertion pada akhir array OK,
jika kita membina array seperti yang kita pergi.

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

34
00:01:33,570 --> 00:01:35,550
berfikir kembali kepada sisipan
jenis, ada banyak

35
00:01:35,550 --> 00:01:37,510
beralih untuk muat unsur di sana.

36
00:01:37,510 --> 00:01:41,170
Dan jadi jika kita akan memasukkan
mana-mana sahaja tetapi 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
>> Begitu juga, penghapusan, kecuali kita
memotong dari akhir array,

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

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

41
00:01:50,790 --> 00:01:54,700
Kami mahu mengeluarkan elemen, dan
maka jenis yang nyaman lagi.

42
00:01:54,700 --> 00:01:57,670
Dan supaya memotong unsur-unsur dari
pelbagai, juga tidak begitu besar.

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

44
00:01:58,820 --> 00:02:00,920
Kami mempunyai akses rawak,
masa pencarian yang berterusan.

45
00:02:00,920 --> 00:02:03,800
Kami hanya mengatakan tujuh, dan kita pergi
kepada pelbagai penempatan semula tujuh.

46
00:02:03,800 --> 00:02:05,907
Kita katakan 20, dengan pergi ke
lokasi penempatan semula 20.

47
00:02:05,907 --> 00:02:07,240
Kami tidak mempunyai untuk melelar seluruh.

48
00:02:07,240 --> 00:02:08,630
Yang cukup baik.

49
00:02:08,630 --> 00:02:11,020
>> Tatasusunan adalah juga agak mudah untuk menyelesaikan.

50
00:02:11,020 --> 00:02:14,040
Setiap kali kita bercakap tentang isihan yang
algoritma, seperti jenis pemilihan,

51
00:02:14,040 --> 00:02:18,820
jenis kemasukan, jenis gelembung, bergabung
jenis, kita sentiasa menggunakan tatasusunan untuk melakukannya,

52
00:02:18,820 --> 00:02:21,860
kerana tatasusunan adalah agak mudah untuk
jenis, relatif kepada struktur data

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

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

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

56
00:02:25,695 --> 00:02:29,210
Anda hanya mengetepikan tepat seperti yang banyak
kerana anda perlu untuk memegang data anda,

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

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

59
00:02:33,180 --> 00:02:36,000
Tetapi Kelemahan lain, walaupun,
adalah bahawa mereka tetap dalam saiz.

60
00:02:36,000 --> 00:02:38,630
Kita perlu mengisytiharkan tepat bagaimana
besar kita mahu pelbagai kami menjadi,

61
00:02:38,630 --> 00:02:39,940
dan kami hanya mendapatkan satu pukulan di dalamnya.

62
00:02:39,940 --> 00:02:41,280
Kita tidak boleh berkembang dan mengecut ia.

63
00:02:41,280 --> 00:02:44,582
>> Jika kita perlu berkembang atau mengecut, kita
perlu mengisytiharkan pelbagai yang baru,

64
00:02:44,582 --> 00:02:47,750
menyalin semua unsur-unsur
lokasi pertama ke lokasi kedua.

65
00:02:47,750 --> 00:02:51,410
Dan jika kita salah mengira bahawa
masa, kita perlu melakukannya sekali lagi.

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

67
00:02:52,760 --> 00:02:58,750
Jadi tatasusunan tidak memberikan kita fleksibiliti
untuk mempunyai nombor berubah unsur-unsur.

68
00:02:58,750 --> 00:03:01,320
>> Dengan senarai berpaut,
kemasukan adalah agak mudah.

69
00:03:01,320 --> 00:03:03,290
Kami hanya jelujur ke hadapan.

70
00:03:03,290 --> 00:03:04,892
Penghapusan adalah juga agak mudah.

71
00:03:04,892 --> 00:03:06,100
Kita perlu mencari 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 sebaik sahaja anda memperolehi unsur
anda cari, semua yang perlu anda lakukan

74
00:03:10,270 --> 00:03:12,830
adalah menukar penunjuk,
mungkin dua jika anda mempunyai

75
00:03:12,830 --> 00:03:15,151
berpaut list-- duanya adalah terpakai
senarai bersambung, rather--

76
00:03:15,151 --> 00:03:16,650
dan kemudian anda hanya boleh membebaskan nod.

77
00:03:16,650 --> 00:03:18,399
Anda tidak perlu untuk beralih
segala-galanya di sekeliling.

78
00:03:18,399 --> 00:03:22,090
Anda hanya menukar dua petunjuk,
jadi itu agak cepat.

79
00:03:22,090 --> 00:03:23,470
>> Lookup tidak baik walaupun, bukan?

80
00:03:23,470 --> 00:03:26,280
Dalam usaha untuk kita untuk mencari
elemen dalam senarai berpaut,

81
00:03:26,280 --> 00:03:29,154
sama ada secara tunggal atau ganda berkaitan,
kita perlu linear mencari ia.

82
00:03:29,154 --> 00:03:32,320
Kita perlu bermula pada awal dan
bergerak tamat, atau bermula dari langkah akhir

83
00:03:32,320 --> 00:03:33,860
untuk permulaan.

84
00:03:33,860 --> 00:03:35,474
Kami tidak mempunyai capaian rawak lagi.

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

86
00:03:37,265 --> 00:03:39,830
senarai berpaut tidak
begitu baik untuk kita.

87
00:03:39,830 --> 00:03:43,750
>> Mereka juga benar-benar
sukar untuk menyelesaikan, bukan?

88
00:03:43,750 --> 00:03:45,666
Satu-satunya cara yang anda boleh
benar-benar menyusun senarai berpaut

89
00:03:45,666 --> 00:03:47,870
adalah untuk menyusun ia seperti yang anda membina ia.

90
00:03:47,870 --> 00:03:50,497
Tetapi jika anda menyusun ia seperti yang anda
membina, 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 tacking
perkara ke hadapan.

93
00:03:53,746 --> 00:03:55,710
Anda perlu mencari
tempat yang betul untuk meletakkan ia,

94
00:03:55,710 --> 00:03:57,820
dan kemudian memasukkan anda
menjadi hanya kira-kira sebagai lapuk

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

96
00:03:59,390 --> 00:04:03,130
Jadi senarai berkaitan tidak
begitu besar untuk menyusun data.

97
00:04:03,130 --> 00:04:05,830
>> Mereka juga agak kecil, saiz Bijaksana.

98
00:04:05,830 --> 00:04:08,496
Senarai duanya adalah terpakai dikaitkan sedikit
lebih besar daripada senarai secara tunggal berkaitan,

99
00:04:08,496 --> 00:04:10,620
yang lebih besar
daripada tatasusunan, tetapi ia tidak

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

101
00:04:13,330 --> 00:04:18,730
Jadi, jika ruang adalah pada premium, tetapi
tidak premium yang benar-benar kuat,

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

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

104
00:04:23,330 --> 00:04:25,850
Memasukkan ke dalam jadual hash
adalah agak mudah.

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

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

107
00:04:30,700 --> 00:04:37,550
dan kemudian kita memasukkan elemen ke dalam
jadual hash di lokasi itu kod hash.

108
00:04:37,550 --> 00:04:40,879
>> Penghapusan, sama dengan senarai bersambung,
mudah sebaik sahaja anda mencari unsur.

109
00:04:40,879 --> 00:04:43,170
Anda perlu mencari ia pertama,
tetapi kemudian apabila anda memadamnya,

110
00:04:43,170 --> 00:04:45,128
anda hanya perlu untuk bertukar-tukar
beberapa petunjuk,

111
00:04:45,128 --> 00:04:47,250
jika anda menggunakan chaining berasingan.

112
00:04:47,250 --> 00:04:49,942
Jika anda menggunakan menyelesaikan sesuatu,
atau jika anda tidak

113
00:04:49,942 --> 00:04:51,650
menggunakan chaining di semua
dalam jadual hash anda,

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

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

116
00:04:57,134 --> 00:04:58,925
Dan menganggap anda tidak
mempunyai apa-apa perlanggaran,

117
00:04:58,925 --> 00:05:01,650
anda boleh memadam dengan cepat.

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

119
00:05:04,930 --> 00:05:06,910
Ia adalah secara purata lebih baik
daripada senarai berkaitan.

120
00:05:06,910 --> 00:05:09,560
Jika anda menggunakan chaining,
anda masih mempunyai senarai berpaut,

121
00:05:09,560 --> 00:05:13,170
yang bermakna anda masih mempunyai
carian merugikan senarai berpaut.

122
00:05:13,170 --> 00:05:18,390
Tetapi oleh kerana anda mengambil dipautkan anda
senarai dan membelah ia lebih 100 atau 1,000

123
00:05:18,390 --> 00:05:25,380
atau n unsur-unsur dalam jadual hash anda, anda berada
senarai berkaitan semua adalah satu-n saiz.

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

125
00:05:27,650 --> 00:05:32,080
Anda telah n dikaitkan senarai sebaliknya
satu senarai berpaut bersaiz n.

126
00:05:32,080 --> 00:05:34,960
>> Dan sebagainya dunia nyata ini berterusan
faktor, yang kita umumnya

127
00:05:34,960 --> 00:05:39,730
tidak bercakap tentang dalam kerumitan masa, ia
tidak benar-benar membuat perbezaan di sini.

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

129
00:05:43,020 --> 00:05:46,780
tetapi panjang senarai
anda sedang mencari melalui

130
00:05:46,780 --> 00:05:50,080
adalah sangat, sangat pendek oleh perbandingan.

131
00:05:50,080 --> 00:05:52,995
Sekali lagi, jika pengasingan adalah anda
Matlamat di sini, hash meja itu

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

133
00:05:54,370 --> 00:05:56,830
Hanya menggunakan array jika menyusun
adalah benar-benar penting kepada anda.

134
00:05:56,830 --> 00:05:58,590
>> Dan mereka boleh menjalankan gamut saiz.

135
00:05:58,590 --> 00:06:01,640
Adalah sukar untuk mengatakan sama ada yang
jadual hash adalah kecil atau besar,

136
00:06:01,640 --> 00:06:04,110
kerana ia benar-benar bergantung kepada
berapa besar jadual hash anda.

137
00:06:04,110 --> 00:06:07,340
Jika anda hanya akan menyimpan
lima elemen dalam jadual hash anda,

138
00:06:07,340 --> 00:06:10,620
dan anda mempunyai jadual hash
dengan 10,000 unsur-unsur di dalamnya,

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

140
00:06:12,614 --> 00:06:15,030
Kontras yang anda juga boleh
mempunyai jadual hash sangat padat,

141
00:06:15,030 --> 00:06:18,720
tetapi jadual hash anda yang lebih kecil mendapat,
semakin lama setiap orang-orang senarai berkaitan

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

143
00:06:19,220 --> 00:06:22,607
Dan sebagainya ada benar-benar ada cara untuk menentukan
tepat saiz jadual hash,

144
00:06:22,607 --> 00:06:24,440
tetapi ia mungkin selamat
untuk mengatakan ia biasanya

145
00:06:24,440 --> 00:06:27,990
akan menjadi lebih besar daripada yang dikaitkan
senarai menyimpan data yang sama,

146
00:06:27,990 --> 00:06:30,400
tetapi lebih kecil daripada indone a.

147
00:06:30,400 --> 00:06:32,720
>> Dan cuba yang keempat
struktur ini

148
00:06:32,720 --> 00:06:34,070
yang kita telah bercakap tentang.

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

150
00:06:36,450 --> 00:06:38,400
Ada banyak yang dinamik
peruntukan memori,

151
00:06:38,400 --> 00:06:40,780
terutama di awal,
kerana anda mula membina.

152
00:06:40,780 --> 00:06:43,700
Tetapi ia adalah masa yang berterusan.

153
00:06:43,700 --> 00:06:47,690
Ia hanya elemen manusia
di sini yang menjadikan ia rumit.

154
00:06:47,690 --> 00:06:53,250
Mempunyai untuk menghadapi penunjuk 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
Jenis faktor ugutan
petunjuk dalam peruntukan memori dinamik

157
00:06:58,880 --> 00:07:00,130
adalah halangan untuk membersihkan.

158
00:07:00,130 --> 00:07:04,550
Tetapi sebaik sahaja anda telah dibersihkan itu, kemasukan
sebenarnya datang agak mudah,

159
00:07:04,550 --> 00:07:06,810
dan sudah pasti masa yang berterusan.

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

161
00:07:07,680 --> 00:07:11,330
Semua yang anda perlu lakukan adalah mengemudi ke bawah
beberapa petunjuk dan bebas nod,

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

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

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

165
00:07:16,780 --> 00:07:19,924
Jadi, jika semua data anda
lima rentetan aksara,

166
00:07:19,924 --> 00:07:22,590
sebagai contoh, anda menyimpan lima
rentetan aksara di indone anda,

167
00:07:22,590 --> 00:07:25,439
ia hanya mengambil masa lima langkah untuk
mencari apa yang anda cari.

168
00:07:25,439 --> 00:07:28,480
Lima hanya faktor yang tetap, jadi
lagi, kemasukan, penghapusan, dan pencarian

169
00:07:28,480 --> 00:07:31,670
di sini adalah semua masa yang berterusan, berkesan.

170
00:07:31,670 --> 00:07:34,880
>> Satu lagi perkara ialah indone anda
sebenarnya jenis sudah disusun, bukan?

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

172
00:07:36,800 --> 00:07:40,060
dengan pergi surat melalui surat daripada
utama, atau digit dengan digit kunci,

173
00:07:40,060 --> 00:07:45,084
biasanya, indone anda berakhir menjadi
jenis disusun seperti yang anda membinanya.

174
00:07:45,084 --> 00:07:47,250
Ia tidak benar-benar membuat
akal untuk berfikir tentang menyusun

175
00:07:47,250 --> 00:07:49,874
dengan cara yang sama kita berfikir tentang
dengan tatasusunan atau senarai berkaitan,

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

177
00:07:51,070 --> 00:07:54,780
Tetapi dalam erti kata lain, anda
indone disusun sebagai anda pergi.

178
00:07:54,780 --> 00:07:58,630
>> Kekangan yang timbul, sudah tentu, adalah bahawa
indone yang berkembang menjadi besar.

179
00:07:58,630 --> 00:08:02,970
Dari setiap titik persimpangan, anda mungkin
ada-- jika kunci anda terdiri daripada digit,

180
00:08:02,970 --> 00:08:04,880
anda mempunyai 10 lain
tempat-tempat yang anda boleh pergi, yang

181
00:08:04,880 --> 00:08:07,490
bermakna setiap nod
mengandungi maklumat

182
00:08:07,490 --> 00:08:11,440
mengenai data yang anda mahu untuk menyimpan
di nod, ditambah 10 petunjuk.

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

184
00:08:14,430 --> 00:08:17,220
Jadi ia adalah sekurang-kurangnya 80 bait untuk
setiap nod yang anda buat,

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

186
00:08:19,240 --> 00:08:24,950
Dan jika nod anda adalah
surat dan bukannya angka,

187
00:08:24,950 --> 00:08:27,825
kini anda mempunyai 26 petunjuk
dari setiap lokasi.

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

189
00:08:32,007 --> 00:08:33,840
Dan anda mempunyai modal
dan lowercase-- anda boleh

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

191
00:08:35,381 --> 00:08:37,500
Nod anda boleh mendapatkan benar-benar
besar, dan sebagainya indone yang

192
00:08:37,500 --> 00:08:40,470
sendiri, secara keseluruhan, boleh
mendapatkan benar-benar besar, terlalu.

193
00:08:40,470 --> 00:08:42,630
Jadi, jika ruang adalah pada paras tertinggi
premium pada sistem anda,

194
00:08:42,630 --> 00:08:45,830
indone yang mungkin tidak cara yang betul untuk
pergi, walaupun manfaatnya lain

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

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

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

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