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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Yani CS50 olarak, biz kapalı ettik
Farklı veri yapılarının bir sürü

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

4
00:00:09,180 --> 00:00:11,420
Biz diziler gördük, ve bağlantılı ettik
listeleri ve hash tabloları,

5
00:00:11,420 --> 00:00:15,210
ve çalışır, yığınlar ve kuyruklar.

6
00:00:15,210 --> 00:00:17,579
Biz de biraz öğreneceksiniz
ağaçlar ve kümeler hakkında,

7
00:00:17,579 --> 00:00:20,120
ama gerçekten bunlar hepsi sadece bitirmek
yukarı bir tema üzerine varyasyonlar olmak.

8
00:00:20,120 --> 00:00:22,840
Gerçekten var bu
dört temel fikirlerin tür

9
00:00:22,840 --> 00:00:25,190
Başka her şeyi aşağı kaynatın.

10
00:00:25,190 --> 00:00:28,150
Diziler, bağlı listeler,
hash tabloları ve çalışır.

11
00:00:28,150 --> 00:00:30,720
Ve gibi orada, dedi
onlara varyasyonları vardır,

12
00:00:30,720 --> 00:00:32,720
ama bu güzel
çok özetlemek olacak

13
00:00:32,720 --> 00:00:38,140
Her şey biz konuşacağız
C bakımından bu sınıf ile ilgili olarak

14
00:00:38,140 --> 00:00:40,140
>> Ama nasıl bu doğru, her ölçü kadar mı?

15
00:00:40,140 --> 00:00:44,265
Biz artılarını ve eksilerini hakkında konuştuk
onlara ayrı videoları her,

16
00:00:44,265 --> 00:00:46,390
ancak sayıların çok şey var
etrafında atılan alıyorum.

17
00:00:46,390 --> 00:00:48,723
Genel bir sürü var
düşünceler etrafında atılan alıyorum.

18
00:00:48,723 --> 00:00:51,950
Denemek ve konsolide edelim
Sadece tek bir yerde.

19
00:00:51,950 --> 00:00:55,507
En karşı artılarını tartmak edelim
Eksileri ve düşünün

20
00:00:55,507 --> 00:00:57,340
bu veri yapısını
doğru veri olabilir

21
00:00:57,340 --> 00:01:01,440
Size özel durum için yapı,
Verilerin ne tür depolama ediyoruz.

22
00:01:01,440 --> 00:01:06,625
Sen mutlaka her zaman gerekmez
süper hızlı ekleme, silme kullanın

23
00:01:06,625 --> 00:01:10,761
Bir tray ve arama eğer gerçekten
ekleme ve silme umurumda değil

24
00:01:10,761 --> 00:01:11,260
çok fazla.

25
00:01:11,260 --> 00:01:13,968
Sadece hızlı rastgele gerekiyorsa
erişim, belki bir dizi daha iyidir.

26
00:01:13,968 --> 00:01:15,340
Yani bu damıtmak edelim.

27
00:01:15,340 --> 00:01:18,530
En dört her biri hakkında konuşalım
veri yapılarının önemli türlü

28
00:01:18,530 --> 00:01:21,720
Konuştuğumuz ve ettik
Onlar iyi olabilir zaman sadece görmek,

29
00:01:21,720 --> 00:01:23,340
ve ne zaman onlar kadar iyi olmayabilir.

30
00:01:23,340 --> 00:01:24,610
Yani diziler ile başlayalım.

31
00:01:24,610 --> 00:01:27,300
Ekleme Yani, biraz kötü.

32
00:01:27,300 --> 00:01:31,350
>> Bir dizinin sonuna ekleme, Tamam
Biz giderken biz bir dizi inşa ediyorsanız.

33
00:01:31,350 --> 00:01:33,570
Ama biz eklemek gerekirse
ortasına elemanları,

34
00:01:33,570 --> 00:01:35,550
ekleme geri düşünmek
sıralama, bir çok şey var

35
00:01:35,550 --> 00:01:37,510
orada bir eleman sığacak şekilde kayması.

36
00:01:37,510 --> 00:01:41,170
Ve biz eklemek için gidiyoruz eğer öyleyse
Her yerde ama bir dizi sonu

37
00:01:41,170 --> 00:01:43,590
muhtemelen çok büyük değil.

38
00:01:43,590 --> 00:01:46,710
>> Benzer şekilde, silme, sürece biz konum
Bir dizinin sonundan silme,

39
00:01:46,710 --> 00:01:49,810
belki de bu yüzden büyük değil
Biz boş boşluklar bırakmak istemiyorum,

40
00:01:49,810 --> 00:01:50,790
hangi genellikle biz değil.

41
00:01:50,790 --> 00:01:54,700
Biz bir öğe kaldırmak istiyorsanız, ve
Daha sonra sıralama tekrar rahatını olun.

42
00:01:54,700 --> 00:01:57,670
Ve böylece öğeleri silme
Bir dizi, aynı zamanda çok büyük değil.

43
00:01:57,670 --> 00:01:58,820
>> Arama olsa da, harika.

44
00:01:58,820 --> 00:02:00,920
Biz rastgele erişim,
zaman sabiti arama.

45
00:02:00,920 --> 00:02:03,800
Biz sadece yedi demek, ve biz gitmek
Dizi tehcir yedi.

46
00:02:03,800 --> 00:02:05,907
Biz gitmek ile, 20 say
Dizi tehcir 20.

47
00:02:05,907 --> 00:02:07,240
Biz genelinde yineleme gerekmez.

48
00:02:07,240 --> 00:02:08,630
Bu oldukça iyi.

49
00:02:08,630 --> 00:02:11,020
>> Diziler de sıralamak nispeten kolaydır.

50
00:02:11,020 --> 00:02:14,040
Biz sıralama hakkında konuştuk Her zaman
Böyle seçim tür olarak algoritma,

51
00:02:14,040 --> 00:02:18,820
Ekleme sıralama, kabarcık sıralama, birleştirme
sıralama, her zaman bunu yapmak için diziler kullanılır,

52
00:02:18,820 --> 00:02:21,860
diziler oldukça kolay, çünkü
veri yapıları göreli sıralama,

53
00:02:21,860 --> 00:02:22,970
Şimdiye kadar gördüğüm.

54
00:02:22,970 --> 00:02:24,320
>> Onlar da nispeten küçük konum.

55
00:02:24,320 --> 00:02:25,695
Ekstra alan bir şey yok.

56
00:02:25,695 --> 00:02:29,210
Sadece tam olarak çok kenara
Verilerinizi tutmak gerekir gibi,

57
00:02:29,210 --> 00:02:30,320
ve bu oldukça fazla.

58
00:02:30,320 --> 00:02:33,180
Yani oldukça küçük olduğunu
ve bu şekilde etkili.

59
00:02:33,180 --> 00:02:36,000
Ama başka bir dezavantajı olsa da,
büyüklüklerinin sabit olmasıdır.

60
00:02:36,000 --> 00:02:38,630
Biz tam olarak nasıl beyan etmek zorunda
Büyük biz bizim dizi olmak istiyorum

61
00:02:38,630 --> 00:02:39,940
ve biz sadece ona bir tane vurulmaz.

62
00:02:39,940 --> 00:02:41,280
Biz büyümek ve bunu küçültmek olamaz.

63
00:02:41,280 --> 00:02:44,582
>> Biz büyümek ya da küçültmek için gerekiyorsa, biz
tamamen yeni bir diziyi bildirmek gerekiyor

64
00:02:44,582 --> 00:02:47,750
unsurlarının kopyalayın
İkinci diziye ilk dizi.

65
00:02:47,750 --> 00:02:51,410
Ve biz bu yanlış hesap varsa
zaman, biz tekrar yapmak gerekiyor.

66
00:02:51,410 --> 00:02:52,760
Kadar büyük değil.

67
00:02:52,760 --> 00:02:58,750
Yani diziler bize esneklik vermeyin
elementlerin değişken numaraları için.

68
00:02:58,750 --> 00:03:01,320
>> Bağlı liste ile,
ekleme oldukça kolaydır.

69
00:03:01,320 --> 00:03:03,290
Biz sadece ön yüzüne çakmak.

70
00:03:03,290 --> 00:03:04,892
Silme da oldukça kolaydır.

71
00:03:04,892 --> 00:03:06,100
Biz unsurları bulmak zorundayız.

72
00:03:06,100 --> 00:03:07,270
Bu bazı arama içerir.

73
00:03:07,270 --> 00:03:10,270
>> Ama eleman bulduktan sonra
Eğer yapmanız gereken, tüm arıyoruz

74
00:03:10,270 --> 00:03:12,830
bir işaretçi değiştirmek olduğunu,
muhtemelen iki varsa

75
00:03:12,830 --> 00:03:15,151
Bir çifte list-- bağlanmış
bağlantılı liste, rather--

76
00:03:15,151 --> 00:03:16,650
ve sonra sadece düğüm ücretsiz yapabilirsiniz.

77
00:03:16,650 --> 00:03:18,399
Sen kaydırmaya gerek yok
etrafında her şey.

78
00:03:18,399 --> 00:03:22,090
Sadece, iki işaretçileri değiştirin
böylece oldukça hızlı.

79
00:03:22,090 --> 00:03:23,470
>> Arama doğru olsa kötü mü?

80
00:03:23,470 --> 00:03:26,280
Bize bir bulmak için için
Bağlantılı bir listede elemanı

81
00:03:26,280 --> 00:03:29,154
olup tek veya iki bağlantılı
biz bunu arama doğrusal gerekiyor.

82
00:03:29,154 --> 00:03:32,320
Biz başında başlamak zorunda ve
ucunu hareket ettirmek, ya da son hareket başlatmak

83
00:03:32,320 --> 00:03:33,860
başlangıcına.

84
00:03:33,860 --> 00:03:35,474
Artık rastgele erişim yok.

85
00:03:35,474 --> 00:03:37,265
Biz yapıyoruz, bu yüzden
arama sürü, belki

86
00:03:37,265 --> 00:03:39,830
bağlantılı liste değildir
Bizim için o kadar iyi.

87
00:03:39,830 --> 00:03:43,750
>> Onlar gerçekten de konum
sıralamak zor, değil mi?

88
00:03:43,750 --> 00:03:45,666
Tek yolu yapabilirsiniz
Gerçekten bağlantılı listeyi sıralamak

89
00:03:45,666 --> 00:03:47,870
Bunu inşa olarak sıralamak etmektir.

90
00:03:47,870 --> 00:03:50,497
Ama senin gibi sıralamak eğer
Bunu inşa, artık değilsin

91
00:03:50,497 --> 00:03:51,830
Artık hızlı eklemeleri yaparak.

92
00:03:51,830 --> 00:03:53,746
Sadece teyel değil
Ön üzerine işler.

93
00:03:53,746 --> 00:03:55,710
Sen bulmak zorunda
Doğru nokta koymak için,

94
00:03:55,710 --> 00:03:57,820
ve sonra ekleme
sadece yaklaşık olarak kötü olur

95
00:03:57,820 --> 00:03:59,390
bir diziye ekleme gibi.

96
00:03:59,390 --> 00:04:03,130
Yani bağlı listeler değil
veri sıralama için çok büyük.

97
00:04:03,130 --> 00:04:05,830
>> Onlar da oldukça küçük, boyut-bilge değilsin.

98
00:04:05,830 --> 00:04:08,496
Çifte biraz listesi bağlantılı
tek başına bağlantılı listeler daha büyük,

99
00:04:08,496 --> 00:04:10,620
bu biraz daha büyüktür
diziler daha, ama bu değil

100
00:04:10,620 --> 00:04:13,330
israf alanı büyük miktarda.

101
00:04:13,330 --> 00:04:18,730
Yani uzay prim, ama
değil gerçekten yoğun bir prim,

102
00:04:18,730 --> 00:04:22,180
bu gitmek için doğru yol olabilir.

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

104
00:04:23,330 --> 00:04:25,850
Karma tabloya Yerleştirme
oldukça basittir.

105
00:04:25,850 --> 00:04:26,980
Bu iki aşamalı bir süreçtir.

106
00:04:26,980 --> 00:04:30,700
İlk aracılığıyla veri çalıştırmak için gereken
Bir hash fonksiyonu bir karma kodu almak için,

107
00:04:30,700 --> 00:04:37,550
ve sonra içine öğe eklemek
Bu karma kodu yerde karma tablo.

108
00:04:37,550 --> 00:04:40,879
>> Bağlantılı listeye benzer Silme,
Eğer eleman bulduğunuzda kolaydır.

109
00:04:40,879 --> 00:04:43,170
Sen önce onu bulmak zorunda
ama sonra bunu sildiğinizde,

110
00:04:43,170 --> 00:04:45,128
Sadece alışverişi gerekir
işaretçiler bir çift,

111
00:04:45,128 --> 00:04:47,250
Eğer ayrı zincirleme kullanıyoruz.

112
00:04:47,250 --> 00:04:49,942
Eğer sondalama kullanıyorsanız,
ya sen değilsin eğer

113
00:04:49,942 --> 00:04:51,650
kullanarak tüm zincirleme
senin hash tablosunda,

114
00:04:51,650 --> 00:04:53,040
silme aslında gerçekten çok kolay.

115
00:04:53,040 --> 00:04:57,134
Yapmanız gereken tek şey karma olduğunu
Veri ve o konuma gidin.

116
00:04:57,134 --> 00:04:58,925
Ve varsayarak değil mi
Herhangi bir çarpışmalar

117
00:04:58,925 --> 00:05:01,650
Çok hızlı bir şekilde silmek mümkün olacak.

118
00:05:01,650 --> 00:05:04,930
>> Şimdi, arama nerede şeyler
Biraz daha karmaşık olsun.

119
00:05:04,930 --> 00:05:06,910
Daha iyi ortalama var
bağlantılı listeler daha.

120
00:05:06,910 --> 00:05:09,560
Eğer zincirleme kullanıyorsanız,
Hala bir bağlantılı liste var,

121
00:05:09,560 --> 00:05:13,170
hangi hala var demektir
Arama bağlantılı liste zarar veren.

122
00:05:13,170 --> 00:05:18,390
Eğer alıyorsun çünkü senin bağlantılı
listesi ve 100 veya 1000 üzerinde bölme

123
00:05:18,390 --> 00:05:25,380
veya n da karma tablo elemanları, sen
bağlı listeler boyutu inci hepsi biridir.

124
00:05:25,380 --> 00:05:27,650
Hepsi önemli ölçüde daha küçük olduğunu.

125
00:05:27,650 --> 00:05:32,080
Sen n yerine listeleri bağladığınız
n büyüklüğünde bir bağlantılı liste.

126
00:05:32,080 --> 00:05:34,960
>> Ve böylece bu gerçek dünya sürekli
Genellikle biz faktörü,

127
00:05:34,960 --> 00:05:39,730
Zaman karmaşıklığı hakkında konuşmak yok, o
Aslında burada bir fark yoktur.

128
00:05:39,730 --> 00:05:43,020
Yani arama hala doğrusal
Eğer zincirleme kullanıyorsanız arama

129
00:05:43,020 --> 00:05:46,780
ancak listenin uzunluğu
Üzerinden aradığınız

130
00:05:46,780 --> 00:05:50,080
kıyasla çok kısadır.

131
00:05:50,080 --> 00:05:52,995
Yine, sınıflandırıp ise,
Burada amaç, karma tablo en

132
00:05:52,995 --> 00:05:54,370
Muhtemelen doğru yolu gitmek için değil.

133
00:05:54,370 --> 00:05:56,830
Sıralama eğer sadece bir dizi kullanmak
Sizin için çok önemli.

134
00:05:56,830 --> 00:05:58,590
>> Ve onlar büyüklük gam çalıştırabilirsiniz.

135
00:05:58,590 --> 00:06:01,640
Bir olmadığını söylemek zor
hash tablosu, küçük ya da büyük

136
00:06:01,640 --> 00:06:04,110
Gerçekten bağlıdır çünkü
ne kadar büyük senin karma tablodur.

137
00:06:04,110 --> 00:06:07,340
Sadece depolamak için gidiyoruz
senin hash tablosunda beş element,

138
00:06:07,340 --> 00:06:10,620
ve bir karma tablo var
İçinde 10.000 elemanları ile,

139
00:06:10,620 --> 00:06:12,614
muhtemelen çok yer harcıyorsun.

140
00:06:12,614 --> 00:06:15,030
Kontrast ayrıca yapabilirsiniz olmak
, çok kompakt hash tabloları var

141
00:06:15,030 --> 00:06:18,720
ama daha küçük senin hash tablosu, gets
Bu bağlantılı listeler, her uzun

142
00:06:18,720 --> 00:06:19,220
alır.

143
00:06:19,220 --> 00:06:22,607
Ve bu yüzden gerçekten tanımlamak için hiçbir yolu yoktur
Tam bir karma tablosu boyutu

144
00:06:22,607 --> 00:06:24,440
ama muhtemelen güvenli
genellikle söylemek

145
00:06:24,440 --> 00:06:27,990
Bağlantılı daha büyük olacak
Aynı veri depolama listesi,

146
00:06:27,990 --> 00:06:30,400
Bir tray daha ancak daha küçük.

147
00:06:30,400 --> 00:06:32,720
>> Ve çalışır dördüncü olan
Bu yapıların

148
00:06:32,720 --> 00:06:34,070
biz bahsediyoruz oldum.

149
00:06:34,070 --> 00:06:36,450
Bir tray takmadan karmaşıktır.

150
00:06:36,450 --> 00:06:38,400
Dinamik bir sürü var
bellek ayırma,

151
00:06:38,400 --> 00:06:40,780
Özellikle başında,
inşa etmek başlıyoruz olarak.

152
00:06:40,780 --> 00:06:43,700
Ama sürekli zamanı.

153
00:06:43,700 --> 00:06:47,690
Bu sadece insan unsuru var
Burada zor hale getirdiğini.

154
00:06:47,690 --> 00:06:53,250
Null işaretçi karşılaşmaya olması, malloc
uzay, muhtemelen malloc uzay oraya gitmek

155
00:06:53,250 --> 00:06:54,490
Oradan tekrar.

156
00:06:54,490 --> 00:06:58,880
Sindirme faktörü tür
dinamik bellek tahsisi işaretçileri

157
00:06:58,880 --> 00:07:00,130
temizlemek için engeldir.

158
00:07:00,130 --> 00:07:04,550
Ama bunu bir kez temizlenir, ekleme
aslında oldukça basit geliyor

159
00:07:04,550 --> 00:07:06,810
ve kesinlikle sabit zamanıdır.

160
00:07:06,810 --> 00:07:07,680
>> Silme kolaydır.

161
00:07:07,680 --> 00:07:11,330
Yapmanız gereken tek şey aşağı gezinmek bir
işaretçiler ve ücretsiz düğümün çift,

162
00:07:11,330 --> 00:07:12,420
böylece oldukça iyi.

163
00:07:12,420 --> 00:07:13,930
Arama da oldukça hızlı.

164
00:07:13,930 --> 00:07:16,780
Sadece tabanlıdır
verilerinizin uzunluğu.

165
00:07:16,780 --> 00:07:19,924
Tüm verilerinizi Yani eğer
Beş karakter dizeleri,

166
00:07:19,924 --> 00:07:22,590
Örneğin, beş saklıyoruz
senin tray karakter dizeleri,

167
00:07:22,590 --> 00:07:25,439
sadece beş adımlar atması
Eğer aradığınızı bulacaksınız.

168
00:07:25,439 --> 00:07:28,480
Beş yüzden, sadece sabit bir faktördür
Yine, ekleme, silme ve arama

169
00:07:28,480 --> 00:07:31,670
Burada etkili tüm sabit zaman vardır.

170
00:07:31,670 --> 00:07:34,880
>> Başka bir şey tray olduğunu
aslında tür zaten sağ sıralanır?

171
00:07:34,880 --> 00:07:36,800
Biz konum nasıl sayesinde
ekleme elemanları,

172
00:07:36,800 --> 00:07:40,060
bir harfi giderek
anahtarın rakamı ile anahtar veya rakam,

173
00:07:40,060 --> 00:07:45,084
genellikle, senin tray olmak biter
Bunu kurmak gibi tür sıralanır.

174
00:07:45,084 --> 00:07:47,250
Gerçekten yapar değil
duygusu sıralama düşünmek

175
00:07:47,250 --> 00:07:49,874
aynı şekilde biz düşünmek
bu diziler, veya bağlantılı listeleri,

176
00:07:49,874 --> 00:07:51,070
veya karma tablolar.

177
00:07:51,070 --> 00:07:54,780
Ancak bazı anlamda, sizin
Eğer gitmek gibi tray sıralanır.

178
00:07:54,780 --> 00:07:58,630
>> Olumsuz, tabii ki, yani
bir tray hızlı büyük hale gelir.

179
00:07:58,630 --> 00:08:02,970
Her kavşak noktadan itibaren, belki
anahtar rakamlardan oluşuyorsa have--,

180
00:08:02,970 --> 00:08:04,880
Diğer 10 var
yerleştirir, gidebilirsin ki

181
00:08:04,880 --> 00:08:07,490
Her düğümün demektir
bilgi içerir

182
00:08:07,490 --> 00:08:11,440
veriler hakkında Saklamak istediğiniz
bu düğüm, artı 10 işaretçileri de.

183
00:08:11,440 --> 00:08:14,430
Hangi CS50 IDE, 80 bayt.

184
00:08:14,430 --> 00:08:17,220
Bu yüzden en az 80 bayt var
Oluşturduğunuz her düğüm,

185
00:08:17,220 --> 00:08:19,240
ve hatta veri sayma değil.

186
00:08:19,240 --> 00:08:24,950
Ve düğümler ise
yerine basamak mektupları,

187
00:08:24,950 --> 00:08:27,825
şimdi 26 işaretçiler var
Her yerden.

188
00:08:27,825 --> 00:08:32,007
Ve 26 kat 8 muhtemelen 200
bayt, ya da onun gibi bir şey.

189
00:08:32,007 --> 00:08:33,840
Ve sermayeye sahip
ve size yapabilirsiniz lowercase--

190
00:08:33,840 --> 00:08:35,381
Ben bu ile gidiyorum nereye doğru, gördün mü?

191
00:08:35,381 --> 00:08:37,500
Sizin düğümler gerçekten alabilirsiniz
Büyük ve böylece tray

192
00:08:37,500 --> 00:08:40,470
kendisi, genel olarak, can
çok gerçekten büyük olsun.

193
00:08:40,470 --> 00:08:42,630
Uzay yüksek olan yani eğer
Sisteminizde prim,

194
00:08:42,630 --> 00:08:45,830
Bir tray doğru yol olmayabilir
Hatta onun diğer faydaları olsa da, gitmek

195
00:08:45,830 --> 00:08:47,780
oyuna gel.

196
00:08:47,780 --> 00:08:48,710
Ben Doug Lloyd değilim.

197
00:08:48,710 --> 00:08:50,740
Bu CS50 olduğunu.

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