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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Belə ki, CS50, biz əhatə etdik
müxtəlif data strukturları bir çox,

3
00:00:08,300 --> 00:00:09,180
sağ?

4
00:00:09,180 --> 00:00:11,420
Biz Diziler görünür və bağlı etdik
siyahıları, və hash masalar,

5
00:00:11,420 --> 00:00:15,210
və çalışır, bacalar və sıralarında.

6
00:00:15,210 --> 00:00:17,579
Biz də bir az öyrənmək lazımdır
ağac və vaxt haqqında

7
00:00:17,579 --> 00:00:20,120
lakin, həqiqətən, bu bütün yalnız son
up mövzusunda varyasyonları olan.

8
00:00:20,120 --> 00:00:22,840
Həqiqətən var bu
dörd əsas fikir cür

9
00:00:22,840 --> 00:00:25,190
başqa hər şey aşağı qaynatmaq bilər.

10
00:00:25,190 --> 00:00:28,150
Diziler, bağlı siyahıları,
hash masalar və çalışır.

11
00:00:28,150 --> 00:00:30,720
Və kimi orada ifadə edərək,
onlara varyasyonları,

12
00:00:30,720 --> 00:00:32,720
lakin bu olduqca
qədər yekunlaşdırmaq niyyətində

13
00:00:32,720 --> 00:00:38,140
hər şey danışmaq olacaq
C. baxımından bu sinif haqqında

14
00:00:38,140 --> 00:00:40,140
>> Amma necə bu doğru, bütün tədbir up edirsiniz?

15
00:00:40,140 --> 00:00:44,265
Biz lehte ve eksiklikleri haqqında söhbət etdik
onlara ayrı-ayrı video hər,

16
00:00:44,265 --> 00:00:46,390
lakin nömrələri bir çox var
ətrafında atılan almaq.

17
00:00:46,390 --> 00:00:48,723
Ümumi bir çox var
fikirlər ətrafında atılan almaq.

18
00:00:48,723 --> 00:00:51,950
Nin cəhd və birləşdirmək edək
yalnız bir yerdə.

19
00:00:51,950 --> 00:00:55,507
Nin qarşı müsbət çəkin edək
eksiklikleri, və hesab

20
00:00:55,507 --> 00:00:57,340
olan data structure
Sağ data ola bilər

21
00:00:57,340 --> 00:01:01,440
xüsusi vəziyyət üçün strukturu,
məlumatların nə cür saxlanılması edirik.

22
00:01:01,440 --> 00:01:06,625
Siz mütləq həmişə ehtiyac yoxdur
, super sürətli durub, silinməsi istifadə

23
00:01:06,625 --> 00:01:10,761
bir trie və axtarış əgər həqiqətən
daxil və silmə haqqında qayğı yoxdur

24
00:01:10,761 --> 00:01:11,260
həddindən artıq çox.

25
00:01:11,260 --> 00:01:13,968
Yalnız tez təsadüfi ehtiyac varsa
giriş, bəlkə bir sıra daha yaxşıdır.

26
00:01:13,968 --> 00:01:15,340
Belə ki, çəkmək edək.

27
00:01:15,340 --> 00:01:18,530
Dörd hər biri haqqında danışmaq edək
data strukturları əsas növ

28
00:01:18,530 --> 00:01:21,720
biz danışdıq və etdik ki,
Onlar yaxşı ola bilər zaman yalnız görmək,

29
00:01:21,720 --> 00:01:23,340
və onlar belə yaxşı ola bilər.

30
00:01:23,340 --> 00:01:24,610
Belə ki, Diziler ilə başlamaq edək.

31
00:01:24,610 --> 00:01:27,300
Durub Belə ki, bu cür pis.

32
00:01:27,300 --> 00:01:31,350
>> Bir sıra sonunda durub, OK
biz getmək kimi biz bir sıra tikinti edirsinizsə.

33
00:01:31,350 --> 00:01:33,570
Amma biz daxil etmək lazımdır, əgər
orta elementləri,

34
00:01:33,570 --> 00:01:35,550
durub geri edirəm
sort, bir çox var

35
00:01:35,550 --> 00:01:37,510
orada bir element uyğun dəyişir.

36
00:01:37,510 --> 00:01:41,170
Və biz daxil olacaq əgər
hər hansı lakin bir sıra sonu,

37
00:01:41,170 --> 00:01:43,590
yəqin ki, belə böyük deyil.

38
00:01:43,590 --> 00:01:46,710
>> Eynilə, silinməsi, əgər biz istəyirik
bir sıra sonunda silmə,

39
00:01:46,710 --> 00:01:49,810
yəqin ki, həmçinin əgər belə böyük deyil
biz boş boşluqları tərk etmək istəmirəm,

40
00:01:49,810 --> 00:01:50,790
adətən biz deyil.

41
00:01:50,790 --> 00:01:54,700
Biz bir element aradan qaldırılması istəyirsinizsə, və
sonra sort yenidən rahat edir.

42
00:01:54,700 --> 00:01:57,670
Və belə elementləri silmə
bir sıra da o qədər də böyük deyil.

43
00:01:57,670 --> 00:01:58,820
>> Axtarış, baxmayaraq ki, böyükdür.

44
00:01:58,820 --> 00:02:00,920
Biz təsadüfi imkanı var,
daimi vaxt Sistemi.

45
00:02:00,920 --> 00:02:03,800
Biz yalnız yeddi demək, və biz getmək
array köçürülməsi yeddi.

46
00:02:03,800 --> 00:02:05,907
Biz yolda ilə 20 demək
array köçürülməsi 20.

47
00:02:05,907 --> 00:02:07,240
Biz arasında təkrarlamaq yoxdur.

48
00:02:07,240 --> 00:02:08,630
Bu olduqca yaxşı.

49
00:02:08,630 --> 00:02:11,020
>> Diziler də düzmək üçün nisbətən asandır.

50
00:02:11,020 --> 00:02:14,040
Biz çeşidlənməsi haqqında danışdı Hər zaman
Belə seçim sort kimi alqoritm,

51
00:02:14,040 --> 00:02:18,820
durub sort, bubble sort, birləşməsi
sort, biz həmişə bunu Diziler istifadə

52
00:02:18,820 --> 00:02:21,860
Diziler olduqca asandır, çünki
data strukturları nisbətən sort,

53
00:02:21,860 --> 00:02:22,970
Biz bu günə qədər gördüm.

54
00:02:22,970 --> 00:02:24,320
>> Onlar həmçinin nisbətən kiçik istəyirik.

55
00:02:24,320 --> 00:02:25,695
Əlavə yer bir çox deyil.

56
00:02:25,695 --> 00:02:29,210
Siz yalnız tam olaraq çox kənara
sizin data keçirmək lazımdır ki,

57
00:02:29,210 --> 00:02:30,320
və bu olduqca çox var.

58
00:02:30,320 --> 00:02:33,180
Belə ki, onlar olduqca kiçik istəyirik,
və o şəkildə səmərəli.

59
00:02:33,180 --> 00:02:36,000
Amma başqa İşin mənfi tərəfi odur, baxmayaraq ki,
Onlar ölçüsü müəyyən olunur.

60
00:02:36,000 --> 00:02:38,630
Biz necə dəqiq elan var
big biz array olmaq istəyirəm

61
00:02:38,630 --> 00:02:39,940
və biz yalnız bir shot almaq.

62
00:02:39,940 --> 00:02:41,280
Biz inkişaf və shrink bilməz.

63
00:02:41,280 --> 00:02:44,582
>> Biz bunu inkişaf və ya shrink ehtiyac varsa, biz
tamamilə yeni array bəyan etmək lazımdır,

64
00:02:44,582 --> 00:02:47,750
elementlərinin bütün surəti
ikinci sıra ilk array.

65
00:02:47,750 --> 00:02:51,410
Və biz miscalculated əgər
vaxt, biz yenə bunu etmək lazımdır.

66
00:02:51,410 --> 00:02:52,760
Belə böyük deyil.

67
00:02:52,760 --> 00:02:58,750
Belə ki, seriallarda, bizə rahatlıq vermir
elementlərin dəyişən nömrələri var.

68
00:02:58,750 --> 00:03:01,320
>> Bir bağlı siyahı ilə,
durub olduqca asandır.

69
00:03:01,320 --> 00:03:03,290
Biz yalnız qarşısında üzərinə tack.

70
00:03:03,290 --> 00:03:04,892
Deletion də olduqca asandır.

71
00:03:04,892 --> 00:03:06,100
Biz elementləri tapmaq lazımdır.

72
00:03:06,100 --> 00:03:07,270
Ki, bir axtarış daxildir.

73
00:03:07,270 --> 00:03:10,270
>> Amma element gördük
Siz nə etmək lazımdır Bütün aradığınız

74
00:03:10,270 --> 00:03:12,830
bir göstərici dəyişdirmək deyil,
bəlkə iki varsa

75
00:03:12,830 --> 00:03:15,151
bir ikiqat list-- bağlıdır
bağlı siyahısı, rather--

76
00:03:15,151 --> 00:03:16,650
və sonra yalnız node azad edə bilər.

77
00:03:16,650 --> 00:03:18,399
Siz keçmək yoxdur
ətrafında hər şey.

78
00:03:18,399 --> 00:03:22,090
Siz yalnız iki göstəricilərinə dəyişə
belə ki, olduqca sürətli var.

79
00:03:22,090 --> 00:03:23,470
>> Axtarış doğru olsa pis?

80
00:03:23,470 --> 00:03:26,280
Bizə bir tapmaq üçün üçün
bir bağlı siyahısında element,

81
00:03:26,280 --> 00:03:29,154
olub story və ya ikiqat, bağlı
biz axtarış xətti var.

82
00:03:29,154 --> 00:03:32,320
Biz əvvəlində başlamaq lazımdır və
son hərəkət, və ya son hərəkət-da başlayacaq

83
00:03:32,320 --> 00:03:33,860
əvvəlinə.

84
00:03:33,860 --> 00:03:35,474
Biz artıq təsadüfi çıxışı yoxdur.

85
00:03:35,474 --> 00:03:37,265
Biz edirik Belə ki
axtarış çox, bəlkə

86
00:03:37,265 --> 00:03:39,830
bir bağlı siyahısı deyil
bizim üçün kifayət qədər yaxşı.

87
00:03:39,830 --> 00:03:43,750
>> Onlar, həqiqətən, də istəyirik
düzmək üçün çətin, sağ?

88
00:03:43,750 --> 00:03:45,666
yeganə yolu siz
həqiqətən bağlı siyahı düzmək

89
00:03:45,666 --> 00:03:47,870
Siz onu tikmək kimi düzmək üçün.

90
00:03:47,870 --> 00:03:50,497
Amma sizin kimi bu sort əgər
onu tikintisi, artıq istəyirik

91
00:03:50,497 --> 00:03:51,830
Artıq tez insertions edilməsi.

92
00:03:51,830 --> 00:03:53,746
Siz yalnız tacking deyilik
qarşısında üzərinə şeylər.

93
00:03:53,746 --> 00:03:55,710
Siz tapmaq lazımdır
sağ spot qoymaq üçün,

94
00:03:55,710 --> 00:03:57,820
və sonra durub
yalnız pis olur

95
00:03:57,820 --> 00:03:59,390
bir sıra daxil daxil kimi.

96
00:03:59,390 --> 00:04:03,130
Belə ki, bağlı siyahıları deyil
məlumat çeşidlənməsi üçün belə böyük.

97
00:04:03,130 --> 00:04:05,830
>> Onlar həmçinin olduqca kiçik, ölçüsü-müdrik istəyirik.

98
00:04:05,830 --> 00:04:08,496
Ikiqat az siyahısını bağlıdır
story bağlı siyahıları daha böyük,

99
00:04:08,496 --> 00:04:10,620
olan qədər böyük
Diziler daha lakin bu deyil

100
00:04:10,620 --> 00:04:13,330
sərf kosmik böyük məbləği.

101
00:04:13,330 --> 00:04:18,730
Belə ki, əgər yer bir mükafat, lakin
Biz, həqiqətən sıx premium,

102
00:04:18,730 --> 00:04:22,180
Bu getmək üçün doğru yol ola bilər.

103
00:04:22,180 --> 00:04:23,330
>> Hash masalar.

104
00:04:23,330 --> 00:04:25,850
Bir hash masa durub
kifayət qədər sadə deyil.

105
00:04:25,850 --> 00:04:26,980
Bu iki addım prosesi var.

106
00:04:26,980 --> 00:04:30,700
Birinci biz vasitəsilə data run lazımdır
bir hash funksiyası hash kodu almaq üçün,

107
00:04:30,700 --> 00:04:37,550
və sonra daxil element daxil
ki, hash kodu yerdə hash masa.

108
00:04:37,550 --> 00:04:40,879
>> Bağlı siyahı oxşar Deletion,
Siz element tapmaq bir dəfə asandır.

109
00:04:40,879 --> 00:04:43,170
Siz ilk tapmaq lazımdır
lakin sonra onu silmək zaman,

110
00:04:43,170 --> 00:04:45,128
Yalnız mübadiləsi etmək lazımdır
göstəricilərinə bir neçə

111
00:04:45,128 --> 00:04:47,250
Əgər ayrı-ayrı chaining istifadə edirik.

112
00:04:47,250 --> 00:04:49,942
Siz probing istifadə edirsinizsə,
və ya değilseniz

113
00:04:49,942 --> 00:04:51,650
istifadə edərək, bütün chaining
Sizin hash masa,

114
00:04:51,650 --> 00:04:53,040
silinməsi, həqiqətən, həqiqətən asandır.

115
00:04:53,040 --> 00:04:57,134
Siz nə etmək lazımdır Bütün hash edir
data, sonra yere gedin.

116
00:04:57,134 --> 00:04:58,925
Və fərz siz deyil
Hər hansı bir toqquşma var

117
00:04:58,925 --> 00:05:01,650
çox tez silmək mümkün olacaq.

118
00:05:01,650 --> 00:05:04,930
>> İndi axtarış harada şeyi edir
bir az daha mürəkkəb almaq.

119
00:05:04,930 --> 00:05:06,910
Bu daha yaxşı orta hesabla var
bağlı siyahıları çox.

120
00:05:06,910 --> 00:05:09,560
Siz zəncirləmə istifadə edirsinizsə,
Siz hələ bir bağlı siyahı var,

121
00:05:09,560 --> 00:05:13,170
siz hələ var deməkdir
Axtarış bağlı siyahı zərərinə.

122
00:05:13,170 --> 00:05:18,390
Siz alaraq edirik, çünki ancaq bağlıdır
siyahısı və 100 və ya 1000-dən artıq parçalanması

123
00:05:18,390 --> 00:05:25,380
və ya n sizin hash cədvəldə elementləri, etdiyiniz
bağlı siyahıları ölçüsü nth bütün biridir.

124
00:05:25,380 --> 00:05:27,650
Onlar bütün əhəmiyyətli dərəcədə kiçik istəyirik.

125
00:05:27,650 --> 00:05:32,080
Siz n əvəzinə siyahıları bağlıdır
ölçüsü n biri bağlı siyahı.

126
00:05:32,080 --> 00:05:34,960
>> Və bu real-dünya daimi
Ümumiyyətlə, biz amil,

127
00:05:34,960 --> 00:05:39,730
vaxt mürəkkəbliyi haqqında danışmaq deyil, onu
həqiqətən, burada bir fərq yoxdur.

128
00:05:39,730 --> 00:05:43,020
Belə ki, axtarış hələ xətti
Siz zəncirləmə kullanıyorsanız axtarış

129
00:05:43,020 --> 00:05:46,780
lakin siyahısı uzunluğu
Siz vasitəsilə axtarış edirik

130
00:05:46,780 --> 00:05:50,080
Müqayisə çox, çox qısa.

131
00:05:50,080 --> 00:05:52,995
Yenə çeşidlənməsi əgər
Burada məqsəd, hash table nin

132
00:05:52,995 --> 00:05:54,370
yəqin ki, doğru yol getmək üçün deyil.

133
00:05:54,370 --> 00:05:56,830
Çeşidlənməsi, yalnız bir sıra istifadə
sizin üçün həqiqətən vacibdir.

134
00:05:56,830 --> 00:05:58,590
>> Onlar ölçüsü gamut çalıştırabilirsiniz.

135
00:05:58,590 --> 00:06:01,640
Bu söyləmək çətindir
hash table, kiçik və ya böyük

136
00:06:01,640 --> 00:06:04,110
bu, həqiqətən asılıdır
necə böyük sizin hash masa.

137
00:06:04,110 --> 00:06:07,340
Yalnız saxlanılması olacaq edirsinizsə
Sizin hash masa beş elementləri,

138
00:06:07,340 --> 00:06:10,620
və bir hash masa var
bu 10.000 elementləri ilə,

139
00:06:10,620 --> 00:06:12,614
Siz yəqin ki, yer çox israf edirik.

140
00:06:12,614 --> 00:06:15,030
Kontrast də bilər olan
, çox yığcam hash masalar var

141
00:06:15,030 --> 00:06:18,720
lakin kiçik Sizin hash masa olur
bu bağlı siyahıları hər artıq

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

143
00:06:19,220 --> 00:06:22,607
Və belə ki, həqiqətən müəyyən etmək üçün heç bir yol var
dəqiq bir hash masa ölçüsü,

144
00:06:22,607 --> 00:06:24,440
lakin yəqin ki, güvenli
ümumiyyətlə demək

145
00:06:24,440 --> 00:06:27,990
Bir bağlı daha böyük olacaq
Eyni data saxlanılması siyahısı

146
00:06:27,990 --> 00:06:30,400
bir trie daha lakin kiçik.

147
00:06:30,400 --> 00:06:32,720
>> Və çalışır dördüncü var
bu strukturların

148
00:06:32,720 --> 00:06:34,070
ki, biz söhbət etdik.

149
00:06:34,070 --> 00:06:36,450
Bir trie daxil daxil mürəkkəbdir.

150
00:06:36,450 --> 00:06:38,400
Dinamik bir çox var
yaddaş ayrılması,

151
00:06:38,400 --> 00:06:40,780
xüsusilə əvvəlində,
Siz qurmaq üçün başlanğıc etdiyiniz kimi.

152
00:06:40,780 --> 00:06:43,700
Amma bu, daimi vaxt var.

153
00:06:43,700 --> 00:06:47,690
Bu, yalnız insan element var
burada çətin ki.

154
00:06:47,690 --> 00:06:53,250
Null göstərici qarşılaşmağa olan malloc
space, bəlkə malloc yer getmək

155
00:06:53,250 --> 00:06:54,490
oradan yenidən.

156
00:06:54,490 --> 00:06:58,880
qorxudulması amilinin sort
dinamik yaddaş ayrılması göstəricilər

157
00:06:58,880 --> 00:07:00,130
sil mane deyil.

158
00:07:00,130 --> 00:07:04,550
Amma siz bunu tip sonra, durub
həqiqətən, olduqca sadə gəlir

159
00:07:04,550 --> 00:07:06,810
və əlbəttə ki, daimi vaxt.

160
00:07:06,810 --> 00:07:07,680
>> Deletion asandır.

161
00:07:07,680 --> 00:07:11,330
Siz nə etmək lazımdır Bütün aşağı gedin bir
göstəricilər və node neçə,

162
00:07:11,330 --> 00:07:12,420
belə ki, olduqca yaxşı.

163
00:07:12,420 --> 00:07:13,930
Lookup də olduqca sürətli edir.

164
00:07:13,930 --> 00:07:16,780
Bu, yalnız əsasında
Sizin data uzunluğu.

165
00:07:16,780 --> 00:07:19,924
Sizin data bütün əgər Belə ki,
Beş xarakter strings,

166
00:07:19,924 --> 00:07:22,590
məsələn, beş saxlanılması edirik
Sizin trie xarakter strings,

167
00:07:22,590 --> 00:07:25,439
yalnız beş addımlar atır
Aradığınız nə tapa bilərsiniz.

168
00:07:25,439 --> 00:07:28,480
Beş, belə ki, yalnız bir sabit amildir
yenə durub, silinməsi, və axtarış

169
00:07:28,480 --> 00:07:31,670
burada səmərəli, bütün daimi zaman var.

170
00:07:31,670 --> 00:07:34,880
>> Başqa bir şey sizin trie olduğunu
həqiqətən cür artıq sağ, sıralanır?

171
00:07:34,880 --> 00:07:36,800
Biz ne əsasında
daxil elementləri,

172
00:07:36,800 --> 00:07:40,060
bir məktub məktubu gedən
əsas pillə əsas və ya rəqəmli,

173
00:07:40,060 --> 00:07:45,084
adətən, sizin trie olan qədər başa
Siz qurmaq kimi cür sıralanır.

174
00:07:45,084 --> 00:07:47,250
Bu, həqiqətən edir deyil
mənada çeşidlənməsi haqqında düşünmək

175
00:07:47,250 --> 00:07:49,874
eyni şəkildə biz düşünmək
Bu serialların və ya bağlı siyahıları ilə,

176
00:07:49,874 --> 00:07:51,070
və ya hash masalar.

177
00:07:51,070 --> 00:07:54,780
Lakin bəzi mənada, sizin
Siz getmək kimi trie çeşidlənir.

178
00:07:54,780 --> 00:07:58,630
>> İşin mənfi tərəfi odur, əlbəttə ki,
bir trie sürətlə böyük olur.

179
00:07:58,630 --> 00:08:02,970
Hər qovşağında baxımdan, siz bilər
əsas rəqəmdən ibarətdir əgər yaxşıdır,

180
00:08:02,970 --> 00:08:04,880
digər 10 var
yerlərdə getmək bilər ki,

181
00:08:04,880 --> 00:08:07,490
hər node o deməkdir ki,
məlumat var

182
00:08:07,490 --> 00:08:11,440
məlumatların saxlamaq istəyirəm
ki node, plus 10 göstəricilər də.

183
00:08:11,440 --> 00:08:14,430
Hansı CS50 IDE on 80 bayt edir.

184
00:08:14,430 --> 00:08:17,220
Belə ki, ən azı 80 bayt var
Yaratmaq hər node,

185
00:08:17,220 --> 00:08:19,240
və hətta data sayılması deyil.

186
00:08:19,240 --> 00:08:24,950
Və qovşaqlarının, əgər
əvəzinə rəqəm məktublar,

187
00:08:24,950 --> 00:08:27,825
indi 26 göstəricilərinə var
hər yerdən.

188
00:08:27,825 --> 00:08:32,007
Və 26 dəfə 8 yəqin ki, 200
bytes, və ya kimi bir şey.

189
00:08:32,007 --> 00:08:33,840
Və kapitalı var
və siz lowercase--

190
00:08:33,840 --> 00:08:35,381
Mən bu ilə gedirəm harada sağ, görmək?

191
00:08:35,381 --> 00:08:37,500
Sizin qovşaqlarının həqiqətən əldə edə bilərsiniz
böyük və belə trie

192
00:08:37,500 --> 00:08:40,470
özü, ümumi, bilərsiniz
çox, həqiqətən böyük almaq.

193
00:08:40,470 --> 00:08:42,630
Space yüksək olduğu halda belə
sistem mükafat,

194
00:08:42,630 --> 00:08:45,830
bir trie doğru yol ola bilər
hətta digər faydaları olsa da, getmək

195
00:08:45,830 --> 00:08:47,780
oyun minir.

196
00:08:47,780 --> 00:08:48,710
Mən Doug Lloyd edirəm.

197
00:08:48,710 --> 00:08:50,740
Bu CS50 edir.

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