1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> KONUŞMACI 1: Pekala, bu
CS50 Bu haftanın beş sonudur.

3
00:00:15,860 --> 00:00:19,220
Ve bu son kez hatırlamak biz
başladı meraklısı verilere bakarak

4
00:00:19,220 --> 00:00:22,310
çözmek için başladı yapılar
tanıtmak başladı sorunlar,

5
00:00:22,310 --> 00:00:25,640
yeni sorunlar, ancak bu anahtarı
parçacığı sıralama oldu biz

6
00:00:25,640 --> 00:00:27,940
düğümden düğüme yapmaya başladı.

7
00:00:27,940 --> 00:00:30,085
Yani tabii ki bu
Bir tek başına bağlantılı liste.

8
00:00:30,085 --> 00:00:31,960
Ve tarafından tek başına, bağlı
Ben sadece bir tane var demek

9
00:00:31,960 --> 00:00:33,380
Bu düğümlerin her biri arasında geçirin.

10
00:00:33,380 --> 00:00:35,890
Eğer meraklısı yapabilirsiniz çıkıyor
çift ​​bağlantılı listeler gibi şeyler

11
00:00:35,890 --> 00:00:38,470
Eğer bir ok var sayede
, her iki yönde gidiş hangi

12
00:00:38,470 --> 00:00:40,320
Belirli verimliliği ile yardımcı olabilir.

13
00:00:40,320 --> 00:00:42,000
Ama bu sorunu çözmüş?

14
00:00:42,000 --> 00:00:43,500
Nedir bu sorun çözmek mi?

15
00:00:43,500 --> 00:00:46,620
Pazartesi günü neden umurunda ki?

16
00:00:46,620 --> 00:00:49,820
Neden, teoride, biz Pazartesi günü umurumda mı?

17
00:00:49,820 --> 00:00:50,630
O ne yapar?

18
00:00:50,630 --> 00:00:51,950
>> HEDEF KİTLE: Biz dinamik olarak yeniden boyutlandırmak olabilir.

19
00:00:51,950 --> 00:00:53,740
>> KONUŞMACI 1: Tamam, biz bu yüzden
dinamik olarak yeniden boyutlandırmak.

20
00:00:53,740 --> 00:00:54,710
Peki ikiniz de yapılır.

21
00:00:54,710 --> 00:00:57,560
Yani dinamik bu yeniden boyutlandırabilirsiniz
Veri yapısı, bir dizi ise,

22
00:00:57,560 --> 00:01:00,760
hatırlama, bir bilmek zorunda
priori ne kadar boşluk istediğiniz

23
00:01:00,760 --> 00:01:03,870
ve biraz daha ihtiyacınız varsa
uzay, şans dışında tür konum.

24
00:01:03,870 --> 00:01:05,560
Sen yepyeni bir dizi oluşturmak zorunda.

25
00:01:05,560 --> 00:01:07,893
Siz tüm taşımak zorunda sizin
birinden diğerine veri

26
00:01:07,893 --> 00:01:10,600
Sonunda eski dizi ücretsiz
yapabilirsiniz ve daha sonra devam edersek.

27
00:01:10,600 --> 00:01:13,891
Hangi sadece çok pahalı hissediyor ve çok
verimsiz ve gerçekten bu olabilir.

28
00:01:13,891 --> 00:01:14,890
Ama bu iyi değil.

29
00:01:14,890 --> 00:01:18,180
Biz bir bedel ödemek, tek neydi
daha belirgin fiyatlar biz

30
00:01:18,180 --> 00:01:20,550
Bağlantılı bir listesini kullanarak ödeme?

31
00:01:20,550 --> 00:01:22,825
>> HEDEF KİTLE: Biz kullanmak zorunda
her biri için çift boşluk.

32
00:01:22,825 --> 00:01:25,200
KONUŞMACI 1: Evet, bu yüzden ihtiyacımız
en az iki katı kadar bir alan olarak.

33
00:01:25,200 --> 00:01:27,700
Aslında, ben fark bu resim en
hatta biraz yanıltıcı,

34
00:01:27,700 --> 00:01:32,200
Çünkü modern bir sürü CS50 IDE
bilgisayarlar, bir işaretçi veya adres

35
00:01:32,200 --> 00:01:33,700
Aslında dört bayt değil.

36
00:01:33,700 --> 00:01:36,090
Bu çok sık bu var
gün, sekiz bayt, burada

37
00:01:36,090 --> 00:01:38,530
dibe demektir çoğu
gerçekte orada dikdörtgenler

38
00:01:38,530 --> 00:01:40,900
iki kat tür
Ben boğuldum Ne kadar büyük,

39
00:01:40,900 --> 00:01:44,409
hangi üç kez olarak kullanıyor demektir
biz başka türlü olabilir kadar boşluk.

40
00:01:44,409 --> 00:01:46,700
Şimdi, aynı zamanda, biz konum
Hala bayt konuşuyor, değil mi?

41
00:01:46,700 --> 00:01:49,140
Biz ille bahsetmiyoruz
megabayt veya gigabayt

42
00:01:49,140 --> 00:01:51,000
Bu verilere sürece yapıların büyük olsun.

43
00:01:51,000 --> 00:01:54,510
>> Ve bu yüzden bugün düşünmeye başlar
Verileri keşfetmek nasıl

44
00:01:54,510 --> 00:01:57,310
daha verimli bir şekilde eğer
Aslında veri büyür.

45
00:01:57,310 --> 00:02:00,360
Ama meşrulaştırılmaz deneyelim
İlk operasyon

46
00:02:00,360 --> 00:02:02,460
Eğer bunlar üzerinde yapabileceğiniz
Veri yapılarının türlü.

47
00:02:02,460 --> 00:02:04,790
Bağlantılı gibi Yani bir şey
Liste genellikle destekler

48
00:02:04,790 --> 00:02:07,514
operasyonlar silmek istiyorum,
takın ve arayın.

49
00:02:07,514 --> 00:02:08,639
Ve ben bu ne demek istiyorsunuz?

50
00:02:08,639 --> 00:02:11,222
Bu sadece, genellikle gelir
insanlar bağlantılı liste kullanıyorsanız,

51
00:02:11,222 --> 00:02:14,287
kendilerinin veya başkasının hayata geçirdi
silme, ekleme gibi fonksiyonları,

52
00:02:14,287 --> 00:02:16,120
ve arama yapabilirsiniz, böylece
aslında bir şey yapmak

53
00:02:16,120 --> 00:02:18,030
veri yapısı ile kullanım için yararlı.

54
00:02:18,030 --> 00:02:20,760
Yani kısaca bir göz atalım
biz uygulamak nasıl at

55
00:02:20,760 --> 00:02:24,530
Bağlantılı bir liste için bazı kod aşağıdaki gibi.

56
00:02:24,530 --> 00:02:27,885
>> Yani bu sadece bazı C kodu,
hatta komple bir program

57
00:02:27,885 --> 00:02:29,260
Gerçekten hızlı bir şekilde çırpılmış söyledi.

58
00:02:29,260 --> 00:02:32,300
Bu dağıtımda çevrimiçi değil
kod, aslında çalışmaz çünkü.

59
00:02:32,300 --> 00:02:33,790
Ama sadece ettik fark
Yorum dedi,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, bir şey var
Orada, orada, bir şey nokta nokta nokta.

61
00:02:36,130 --> 00:02:38,410
Ve Sadece bakalım
sulu kısımlar nelerdir.

62
00:02:38,410 --> 00:02:40,790
Yani üçüncü hatta,
Bu şimdi hatırlamak

63
00:02:40,790 --> 00:02:45,960
son bir düğüm ilan önerdi
Zaman, bu dikdörtgen hedeflerden biridir.

64
00:02:45,960 --> 00:02:48,790
Bu, biz N arayacağım bir int var
ama biz bir şey diyebiliriz,

65
00:02:48,790 --> 00:02:51,920
ve daha sonra bir yapı düğüm yıldızı yanındaki denir.

66
00:02:51,920 --> 00:02:55,520
Ve sadece, ikinci açık olması
çizgi, hat altı tarihinde, o da ne?

67
00:02:55,520 --> 00:02:57,930
Bizim için ne yapıyor?

68
00:02:57,930 --> 00:03:01,044
Kesinlikle daha görünüyor çünkü
bizim her zamanki değişkenler daha şifreli.

69
00:03:01,044 --> 00:03:02,740
>> HEDEF KİTLE: O biri üzerinde hareket yapar.

70
00:03:02,740 --> 00:03:04,650
>> KONUŞMACI 1: It biri üzerinde hareket yapar.

71
00:03:04,650 --> 00:03:08,580
Ve, daha kesin olarak
o adresi saklayacak

72
00:03:08,580 --> 00:03:11,582
olması gerekiyordu düğümün
semantik yanında, değil mi?

73
00:03:11,582 --> 00:03:13,540
Bu yüzden gitmiyor
mutlaka bir şey taşıyın.

74
00:03:13,540 --> 00:03:15,290
Sadece gidiyor
olan bir değeri saklamak

75
00:03:15,290 --> 00:03:17,170
adresi olacak
Bazı diğer düğümün,

76
00:03:17,170 --> 00:03:20,810
Biz yapı söylediğim bu yüzden ve işte
düğüm yıldız, yıldız ifade eden

77
00:03:20,810 --> 00:03:22,370
Bir işaretçi veya bir adres.

78
00:03:22,370 --> 00:03:26,390
Tamam, şimdi biz olduğunu varsayalım eğer
Elimizdeki mevcut bu N ve atalım

79
00:03:26,390 --> 00:03:29,490
başkasının olduğunu varsayalım
tamsayılar bir sürü takılı

80
00:03:29,490 --> 00:03:30,400
bağlantılı liste halinde.

81
00:03:30,400 --> 00:03:35,640
Ve bu bağlantılı liste
Bir noktada tarafından işaret

82
00:03:35,640 --> 00:03:39,040
olan bir değişken olarak adlandırılan liste
Bir parametre olarak burada geçti,

83
00:03:39,040 --> 00:03:43,120
nasıl hattı hakkında gitmek
14 arama uygulayan?

84
00:03:43,120 --> 00:03:45,990
Diğer bir deyişle, uygulama am halinde
Amacı hayatında işlev

85
00:03:45,990 --> 00:03:48,889
Daha sonra bir int ve almaktır
Bağlantılı bir listenin başında,

86
00:03:48,889 --> 00:03:50,430
Bu bağlantılı listesine bir göstericidir.

87
00:03:50,430 --> 00:03:52,992
İlk gibi, ben David kim düşünüyorum
Gönüllü, Pazartesi günü oldu

88
00:03:52,992 --> 00:03:54,700
o işaret edildi
Bütün bağlantılı liste,

89
00:03:54,700 --> 00:03:57,820
biz geçiyoruz sanki bulunuyor
David burada argüman olarak.

90
00:03:57,820 --> 00:03:59,990
Nasıl bu listeyi geçme gidiyorsun?

91
00:03:59,990 --> 00:04:04,640
Peki, bu çıkıyor ki olsa bile
işaretçileri, bize şimdi nispeten yeni

92
00:04:04,640 --> 00:04:07,010
Biz nispeten yapabilirsiniz
delikanlı.

93
00:04:07,010 --> 00:04:09,500
>> Ben devam edeceğim ve
geçici bir değişken beyan

94
00:04:09,500 --> 00:04:12,364
Kongre tarafından sadece gidiyor
için, PTR işaretçisi olarak adlandırılan, ya da

95
00:04:12,364 --> 00:04:14,030
ama istediğiniz her şey diyebiliriz.

96
00:04:14,030 --> 00:04:16,470
Ve ben başlatmak için gidiyorum
listenin başına.

97
00:04:16,470 --> 00:04:20,050
Yani bir tür bu düşünebilirsiniz
Bana öğretmen olarak geçen gün,

98
00:04:20,050 --> 00:04:23,580
tür birisine işaret
gönüllü olarak bizim insanlar arasında.

99
00:04:23,580 --> 00:04:26,470
Yani bu geçici bir değişken değilim
sadece aynı şeye işaret

100
00:04:26,470 --> 00:04:31,390
bizim tesadüfen adlı bu
Gönüllü David de işaret ediyordu.

101
00:04:31,390 --> 00:04:35,440
Şimdi ibre ise
boş değil, çünkü hatırlama

102
00:04:35,440 --> 00:04:40,350
O boş bazı özel gözcü değeri
, listenin sonuna çizmektedir

103
00:04:40,350 --> 00:04:44,280
Ben işaret değilim iken yani
Bizim son gönüllü gibi zemin

104
00:04:44,280 --> 00:04:47,190
oldu, en önde gidelim
ve aşağıdakileri yapın.

105
00:04:47,190 --> 00:04:51,820
Pointer-- Eğer şimdi ben tür istiyorum
Biz öğrenciyle yaptıklarını yapmaya

106
00:04:51,820 --> 00:04:57,410
structure-- işaretçi nokta ise bir sonraki
equals-- işaretçi nokta N, eşit değil ise

107
00:04:57,410 --> 00:05:02,290
Değişken N, eşittir
geçirilen oldu argüman,

108
00:05:02,290 --> 00:05:05,370
sonra ben devam etmek istiyorum
ve gerçek dönmek demek.

109
00:05:05,370 --> 00:05:11,020
Ben içinde sayısı N bulduk
Benim bağlantılı liste düğümlerden biri.

110
00:05:11,020 --> 00:05:13,500
Ama nokta artık
Bu bağlamda çalışır

111
00:05:13,500 --> 00:05:17,260
işaretçi, PTR, çünkü
Gerçekten bir gösterici, bir adres,

112
00:05:17,260 --> 00:05:20,632
biz aslında acayip can
sözdizimi nihayet bir parça kullanın

113
00:05:20,632 --> 00:05:22,590
marka bu tür
Sezgisel hissi ve aslında

114
00:05:22,590 --> 00:05:27,870
gitmek anlamına gelir burada bir ok kullanmak
Orada tamsayı o adresi.

115
00:05:27,870 --> 00:05:30,160
Bu yüzden de çok benzer
Nokta operatörü ruhu,

116
00:05:30,160 --> 00:05:33,860
ancak gösterici bir gösterici değil çünkü
ve gerçek bir yapı kendisi

117
00:05:33,860 --> 00:05:35,380
biz sadece oku kullanın.

118
00:05:35,380 --> 00:05:40,620
>> Yani eğer geçerli düğüm ben,
Geçici değişken, işaret ediyorum

119
00:05:40,620 --> 00:05:43,060
N, ne yapmak istiyorsun değil mi?

120
00:05:43,060 --> 00:05:45,910
Eh, benim insan gönüllüler ile
Geçen gün burada vardı,

121
00:05:45,910 --> 00:05:49,710
İlk insan bir ben değilse
istiyorum ve belki de ikinci insan değil

122
00:05:49,710 --> 00:05:52,660
İstediğim tek ve üçüncüsü, ben
hareketli fiziksel tutmak gerekir.

123
00:05:52,660 --> 00:05:54,690
Gibi nasıl bir liste üzerinden adım mı?

124
00:05:54,690 --> 00:05:57,470
Biz bir dizi vardı, sen
Sadece ben artı artı gibi yaptım.

125
00:05:57,470 --> 00:06:03,660
Ancak bu durumda, bu yeterlidir
Bir sonraki, işaretçi, alır, işaretçi yapmak.

126
00:06:03,660 --> 00:06:07,580
Diğer bir deyişle, bir sonraki alan
sol elin bütün gibi

127
00:06:07,580 --> 00:06:10,880
Pazartesi günü insan gönüllüler
Bazı başka bir düğüme işaret kullanarak idi.

128
00:06:10,880 --> 00:06:12,890
Bunlar sonraki komşuları vardı.

129
00:06:12,890 --> 00:06:17,060
>> Bu listede gezinmek için istiyorsanız,
Ben sadece, artık ben yapmak artı artı yapamam

130
00:06:17,060 --> 00:06:20,120
Bunun yerine söylemek zorunda
Ben, işaretçi, gidiyor

131
00:06:20,120 --> 00:06:24,650
Bir sonraki alan ne olursa olsun eşit,
Bir sonraki alan, sonraki alandır olduğunu

132
00:06:24,650 --> 00:06:28,350
Bu sol ellerin aşağıdaki
Biz sahne işaret vardı o

133
00:06:28,350 --> 00:06:30,000
Bazı sonradan değerlere.

134
00:06:30,000 --> 00:06:32,590
Ve ben üzerinden olsun
bütün o yineleme,

135
00:06:32,590 --> 00:06:39,330
ve nihayet, ben olmaması boş vurdu
Bulunan N yine, ben sadece return false.

136
00:06:39,330 --> 00:06:44,100
Yani yine, biz burada yapıyoruz hepsi,
Bir an önce resmi olarak başına,

137
00:06:44,100 --> 00:06:47,840
işaret ederek başlıyor
muhtemelen listenin başında.

138
00:06:47,840 --> 00:06:50,970
Ve sonra ben kontrol değeri
Ben dokuz eşit arıyorum?

139
00:06:50,970 --> 00:06:52,650
Eğer öyleyse, ben gerçek dönmek ve ben bittim.

140
00:06:52,650 --> 00:06:56,450
Değilse, Elimi güncelleyin
AKA gösterici, işaret

141
00:06:56,450 --> 00:06:59,540
Bir sonraki okunun yerde ve
Daha sonra yanındaki ok konumu,

142
00:06:59,540 --> 00:07:00,480
ve bir sonraki.

143
00:07:00,480 --> 00:07:03,770
Ben sadece bu dizi üzerinden yürüyorum.

144
00:07:03,770 --> 00:07:06,010
>> Yani yine, kimin umurunda?

145
00:07:06,010 --> 00:07:07,861
Gibi bunun için bir madde nedir?

146
00:07:07,861 --> 00:07:10,360
Peki, biz tanıttı hatırlatmak
bir yığın kavramı, hangi

147
00:07:10,360 --> 00:07:15,400
o olduğu gibi soyut bir veri sürece türüdür
bir C şey, bir CS50 şey değil,

148
00:07:15,400 --> 00:07:19,430
bu soyut bir fikirdir, bu fikir
üst üste şeyler istifleme

149
00:07:19,430 --> 00:07:21,820
Bu uygulanabilir
farklı şekillerde salkımları.

150
00:07:21,820 --> 00:07:25,600
Ve biz teklif tek yönlü oldu
Bir dizi ya da bir bağlantılı liste ile.

151
00:07:25,600 --> 00:07:29,570
Ve bir o canonically çıkıyor
Yığın en az iki operasyonları destekler.

152
00:07:29,570 --> 00:07:32,320
Ve buzz kelimeler için, itme
yığına şey itmek,

153
00:07:32,320 --> 00:07:34,770
Yeni bir tepsi gibi
yemekhane, veya pop,

154
00:07:34,770 --> 00:07:39,000
hangi üstteki kaldırmak demektir
yemek yığını arasından tepsi

155
00:07:39,000 --> 00:07:41,500
salonu, ve daha sonra belki bazı
diğer işlemler de.

156
00:07:41,500 --> 00:07:45,770
Peki nasıl yapısını tanımlamak olabilir
Şimdi bir yığın diyorsun değil mi?

157
00:07:45,770 --> 00:07:50,020
>> Peki, biz gereği tüm var
diyorum C. bizim emrinde sözdizimi,

158
00:07:50,020 --> 00:07:53,830
Bana bir tür tanımı vermek
Bir yığının içinde bir yapı,

159
00:07:53,830 --> 00:07:58,030
Ben bölgesinin bir dizi olduğunu söylemek için gidiyorum
Bütün sayıların demet ve ardından boyutu.

160
00:07:58,030 --> 00:08:00,930
Yani diğer bir deyişle, ben istiyorum
kodu uygulamak için,

161
00:08:00,930 --> 00:08:03,830
Gitmeme ve sadece tür izin
Bu ne söylediğini çizin.

162
00:08:03,830 --> 00:08:06,317
Bu söylediğini Yani, bana ver
bir dizi var yapısı,

163
00:08:06,317 --> 00:08:09,400
ve ben, kapasite ne olduğunu bilmiyorum
ben ettik o görünüşte bazı sabit var

164
00:08:09,400 --> 00:08:10,858
başka yerde tanımlanmış ve bu iyi.

165
00:08:10,858 --> 00:08:15,260
Ancak, sadece bir varsayalım
iki, üç, dört, beş.

166
00:08:15,260 --> 00:08:16,700
Yani kapasitesi 5 olduğunu.

167
00:08:16,700 --> 00:08:21,730
Içinde bu eleman benim
yapı numaralarını çağrılır.

168
00:08:21,730 --> 00:08:24,020
Ve sonra bir ihtiyaç
diğer değişken görünüşte

169
00:08:24,020 --> 00:08:27,814
Başlangıçta ben gidiyorum denilen boyut
sıfıra başlatıldı şart.

170
00:08:27,814 --> 00:08:29,730
Hiçbir şey de varsa
yığın, boyut, sıfır

171
00:08:29,730 --> 00:08:31,420
ve sayıları çöp değerleri var.

172
00:08:31,420 --> 00:08:33,450
Ben henüz içeride ne hiçbir fikrim yok.

173
00:08:33,450 --> 00:08:36,059
>> Ben itmek istiyorsanız Yani
yığına şey,

174
00:08:36,059 --> 00:08:40,780
Ben işlev itme çağrı varsayalım, ve
Ben, sayı 50 gibi, 50 itmek demek

175
00:08:40,780 --> 00:08:44,090
nereye önereceğini
Ben bu dizide çizmek?

176
00:08:44,090 --> 00:08:47,124
Beş farklı olası cevaplar var.

177
00:08:47,124 --> 00:08:48,790
Nereye numara 50 itmek istiyor musunuz?

178
00:08:48,790 --> 00:08:51,899
Burada amaç, tekrar, çağrı
Fonksiyon itme, bir argüman iletirsiniz

179
00:08:51,899 --> 00:08:52,940
50, bunu nereye koyacağım?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Beş possible--% 20 şans
bir doğru tahmin.

182
00:08:59,052 --> 00:08:59,896
Evet?

183
00:08:59,896 --> 00:09:00,740
>> HEDEF KİTLE: Uzak doğru.

184
00:09:00,740 --> 00:09:01,990
>> KONUŞMACI 1: Uzak doğru.

185
00:09:01,990 --> 00:09:08,359
% 25 şans var
bir doğru tahmin.

186
00:09:08,359 --> 00:09:09,650
Yani aslında iyi olurdu.

187
00:09:09,650 --> 00:09:12,770
Geleneksel olarak, bir dizi ile söylerim,
Biz genellikle, solda başlamak istiyorum

188
00:09:12,770 --> 00:09:14,519
ama biz kesinlikle olabilir
Sağdaki başlar.

189
00:09:14,519 --> 00:09:17,478
Yani burada spoiler ben olurdu
Muhtemelen solda çizmek için gidiyoruz,

190
00:09:17,478 --> 00:09:20,060
Sadece normal bir dizide nerede gibi
Ben sağa sola gidiyor başlar.

191
00:09:20,060 --> 00:09:21,780
Ama çevirebilirsiniz eğer
aritmetik, ince.

192
00:09:21,780 --> 00:09:23,060
Bu sadece geleneksel değil.

193
00:09:23,060 --> 00:09:24,880
Tamam, ben bir yapmak gerekiyor
ama daha değişiklik.

194
00:09:24,880 --> 00:09:27,710
Şimdi ben bir şey itti ettik
yığına, sırada ne var?

195
00:09:27,710 --> 00:09:29,400
>> Pekala, boyutu artırmak gerekiyor.

196
00:09:29,400 --> 00:09:32,600
Bu yüzden bana öncesinde ve sadece gidelim
Sıfır olan bu güncelleme.

197
00:09:32,600 --> 00:09:35,950
Ve onun yerine şimdi, ben gidiyorum
değerinde tek koymak.

198
00:09:35,950 --> 00:09:39,460
Ve şimdi başka bir itme varsayalım
yığına sayısı 51 gibi.

199
00:09:39,460 --> 00:09:42,680
Eh, ben bir daha yapmak zorunda
boyutuna iki kadardır değişim.

200
00:09:42,680 --> 00:09:46,100
Ve sonra bir tane daha itmek varsayalım
61 gibi yığına sayısı

201
00:09:46,100 --> 00:09:52,530
Şimdi boyutunu güncellemeniz gerekir bir daha
Zaman ve boyut olarak değer 3 olsun.

202
00:09:52,530 --> 00:09:54,690
Ve şimdi pop diyoruz herhalde.

203
00:09:54,690 --> 00:09:57,250
Şimdi kongre tarafından, pop,
bir argüman almaz.

204
00:09:57,250 --> 00:10:00,430
Bir yığın ile, tüm
Tepsi metafor noktası

205
00:10:00,430 --> 00:10:03,450
Eğer takdir yetkisine sahip kalmamasıdır
O tepsiyi gidip, tüm yapabileceğiniz

206
00:10:03,450 --> 00:10:06,330
dan üstteki birini pop olduğunu
Yığın, sırf.

207
00:10:06,330 --> 00:10:08,010
İşte bu veri yapısı böyle yapar.

208
00:10:08,010 --> 00:10:12,250
>> Eğer mantık tarafından Yani
pop ne kapalı geliyor demek?

209
00:10:12,250 --> 00:10:13,080
Yani 61.

210
00:10:13,080 --> 00:10:15,402
Yani gerçekten bilgisayar nedir
bellekte yapacaksın?

211
00:10:15,402 --> 00:10:16,610
Ne benim kod ilgisi var?

212
00:10:16,610 --> 00:10:20,330
Ne önereceğini
Biz ekranda değişiklik?

213
00:10:20,330 --> 00:10:23,410
Ne değiştirmek gerekir?

214
00:10:23,410 --> 00:10:24,960
Maalesef?

215
00:10:24,960 --> 00:10:26,334
Yani biz 61 kurtul.

216
00:10:26,334 --> 00:10:27,500
Yani kesinlikle yapabilirim.

217
00:10:27,500 --> 00:10:28,640
Ve ben 61 kurtulabilirsiniz.

218
00:10:28,640 --> 00:10:30,980
Ve sonra ne diğer
değişim gerçekleşmesi gerekiyor?

219
00:10:30,980 --> 00:10:33,160
Boyutu büyük olasılıkla iki geri gitmek zorunda.

220
00:10:33,160 --> 00:10:34,210
Ve böylece iyi.

221
00:10:34,210 --> 00:10:36,690
Ama bir dakika, büyüklüğü bekleyin
bir an önce üç oldu.

222
00:10:36,690 --> 00:10:38,240
Sadece hızlı bir sağlamlık denetimi yapalım.

223
00:10:38,240 --> 00:10:41,810
Nasıl biz biliyor muydunuz
61 kurtulmak istedim?

224
00:10:41,810 --> 00:10:42,760
Biz haşhaş Çünkü.

225
00:10:42,760 --> 00:10:46,450
Ve bu yüzden bu ikinci özellik boyutu var.

226
00:10:46,450 --> 00:10:48,470
>> Ben, bir dakika bekle
Haftanın iki geri düşünme

227
00:10:48,470 --> 00:10:51,660
bahsediyoruz başladığımda
Bu konum sıfır diziler,

228
00:10:51,660 --> 00:10:55,920
Bu konum biriydi bu yeri oldu
İki, bu konum, üç, dört olduğunu

229
00:10:55,920 --> 00:10:58,460
Göründüğü gibi
büyüklüğü arasındaki ilişki

230
00:10:58,460 --> 00:11:02,780
ve istediğim eleman çıkarmak
diziden sadece ne gibi görünüyor?

231
00:11:02,780 --> 00:11:05,120
Boyut eksi bir.

232
00:11:05,120 --> 00:11:07,786
Ve böylece nasıl insan olarak var
Biz 61 önce gelir biliyorum.

233
00:11:07,786 --> 00:11:09,160
Nasıl bilgisayar bilmek oluyor?

234
00:11:09,160 --> 00:11:11,701
Ne zaman kod nerede muhtemelen
boyutu eksi birini yapmak istiyorum,

235
00:11:11,701 --> 00:11:14,950
böylece üç eksi bir, iki, ve olduğunu
Biz 61 kurtulmak istediğiniz anlamına gelir.

236
00:11:14,950 --> 00:11:18,000
Ve sonra biz gerçekten güncelleyebilirsiniz
o boyutta böylece boyutu artık

237
00:11:18,000 --> 00:11:20,300
Sadece iki üç gider.

238
00:11:20,300 --> 00:11:24,520
Ve sadece bilgiçlik olmak gerekirse, ben gidiyorum
Birazdan, işim olduğunu önerecek?

239
00:11:24,520 --> 00:11:27,660
Sezgisel önerdi
Doğru ben 61 kurtulmalıdır.

240
00:11:27,660 --> 00:11:30,700
Ama yok ben tür
çeşit 61 kurtulmuş?

241
00:11:30,700 --> 00:11:33,790
Ben etkin bir şekilde unuttum
o aslında var.

242
00:11:33,790 --> 00:11:37,680
Eğer okudum ve eğer geri PSET4 düşünüyorum
adli tıp ile ilgili makale, PDF

243
00:11:37,680 --> 00:11:40,780
Biz bu çocuklar okumak, ya da
PSET4 için bu hafta okuyacaktır.

244
00:11:40,780 --> 00:11:44,300
Bu aslında germane olduğunu hatırlayın
bilgisayar adli tıp bütün fikir.

245
00:11:44,300 --> 00:11:47,820
Ne bir bilgisayar genellikle yok olduğunu
bir şey olduğu, sadece, unutur

246
00:11:47,820 --> 00:11:51,300
ama gitmek ve benzeri yok
dışarı veya geçersiz kılma kazımak deneyin

247
00:11:51,300 --> 00:11:54,560
birler ve sıfırlar olan bitler
ya da başka bir rasgele bir desen

248
00:11:54,560 --> 00:11:56,690
Sürece kendinizi bu kadar kasıtlı yok.

249
00:11:56,690 --> 00:11:58,930
Yani sezgi oldu
Tamam, 61 kurtulalım.

250
00:11:58,930 --> 00:12:00,650
Ama gerçekte, biz uğraşmak zorunda değilsiniz.

251
00:12:00,650 --> 00:12:04,040
Biz sadece unutmak gerekir
Bizim boyutunu değiştirerek var.

252
00:12:04,040 --> 00:12:05,662
>> Şimdi bu yığının bir sorun var.

253
00:12:05,662 --> 00:12:07,620
Bazı şeyleri zorlamaya devam ederse
yığına, ne

254
00:12:07,620 --> 00:12:11,167
Açıkçası ne olacak
Sadece birkaç dakika süre içinde?

255
00:12:11,167 --> 00:12:12,500
Biz alanı tükenmeye gidiyoruz.

256
00:12:12,500 --> 00:12:13,580
Ve biz ne yapacağız?

257
00:12:13,580 --> 00:12:14,680
Biz tür mahvoluruz.

258
00:12:14,680 --> 00:12:19,000
Bu uygulama izin vermez
kullanma çünkü bize, dizi yeniden boyutlandırmak

259
00:12:19,000 --> 00:12:21,240
Bu sözdizimi, eğer
Haftanın iki geri düşünmek,

260
00:12:21,240 --> 00:12:23,520
Eğer beyan ettik bir kere
Bir dizinin büyüklüğü,

261
00:12:23,520 --> 00:12:26,780
Henüz nerede bir mekanizma görmedim
Eğer dizinin boyutunu değiştirebilirsiniz.

262
00:12:26,780 --> 00:12:29,020
Ve gerçekten C bu özelliği yoktur.

263
00:12:29,020 --> 00:12:32,524
Derseniz, bana beş ver
Nths, onları aramak sayılar,

264
00:12:32,524 --> 00:12:33,940
Bu onu almak için gidiyoruz hepsi bu.

265
00:12:33,940 --> 00:12:38,790
Bu yüzden Pazartesi gününden itibaren şimdi var
Bir çözüm ifade yeteneği

266
00:12:38,790 --> 00:12:42,480
olsa da, biz sadece oynamak için gereken
Bizim yığının tanımı

267
00:12:42,480 --> 00:12:46,840
Bazı sabit kodlanmış dizi olmamak,
ama sadece bir adres saklamak için.

268
00:12:46,840 --> 00:12:47,890
>> Şimdi neden bu?

269
00:12:47,890 --> 00:12:51,690
Şimdi biz sadece rahat olmak zorunda
Aslında benim program çalıştığında o,

270
00:12:51,690 --> 00:12:53,730
Ben muhtemelen gidiyorum
insan sormak zorunda,

271
00:12:53,730 --> 00:12:55,110
kaç sayı saklamak istiyorsun?

272
00:12:55,110 --> 00:12:56,776
Yani giriş yere gelmek zorunda.

273
00:12:56,776 --> 00:12:59,140
Ama bunu öğrendikten sonra
numara, o zaman ben sadece can

274
00:12:59,140 --> 00:13:02,470
vermek işlevi ne kullanmalıyım
Bana bellek yığın?

275
00:13:02,470 --> 00:13:03,580
Ben malloc kullanabilirsiniz.

276
00:13:03,580 --> 00:13:06,710
Ve ben herhangi bir sayıda söyleyebiliriz
bayt geri bu Nths için istiyorum.

277
00:13:06,710 --> 00:13:10,910
Ve tüm sayıları saklamak zorunda
Bu yapının içinde burada değişken

278
00:13:10,910 --> 00:13:13,480
Ne olmalı?

279
00:13:13,480 --> 00:13:18,440
Gerçekte gider
Bu senaryoda numaralar?

280
00:13:18,440 --> 00:13:21,300
Evet, ilk bir işaretçi
bu bellek öbek bayt

281
00:13:21,300 --> 00:13:24,940
veya daha özel olarak, adres
Bu bayt ilk.

282
00:13:24,940 --> 00:13:27,300
Bu bir ise farketmez
bayt veya milyar bayt,

283
00:13:27,300 --> 00:13:28,890
Ben sadece ilk umurumda gerekir.

284
00:13:28,890 --> 00:13:31,530
Çünkü neyi malloc garantiler ve
İşletim sistemi garanti,

285
00:13:31,530 --> 00:13:34,170
olduğu hafıza I yığın
olsun, bitişik olacak.

286
00:13:34,170 --> 00:13:35,378
Boşluklar orada olacak değil.

287
00:13:35,378 --> 00:13:38,576
Ben 50 için sordum eğer öyleyse
bayt veya 1000 bayt

288
00:13:38,576 --> 00:13:40,450
hepsi olacağız
arka arkaya arkaya.

289
00:13:40,450 --> 00:13:44,500
Ve çok uzun ben, nasıl ne kadar büyük hatırlıyorum
çok ben bilmem gereken, tüm istedi

290
00:13:44,500 --> 00:13:46,230
bu tür ilk adresidir.

291
00:13:46,230 --> 00:13:48,660
>> Yani şimdi biz kod yeteneği var.

292
00:13:48,660 --> 00:13:51,280
Gerçi, o bizi almaya gidiyor
daha fazla zaman, bu kadar yazmak için

293
00:13:51,280 --> 00:13:55,900
şimdiye kadar bu bellek tahsis olabilir
Sadece orada farklı bir adres depolamak

294
00:13:55,900 --> 00:13:59,060
biz bile bir büyük veya isterseniz
belleğin küçük bir yığın.

295
00:13:59,060 --> 00:14:00,170
Yani burada bir ticaret kapalı olarak.

296
00:14:00,170 --> 00:14:01,360
Şimdi dinamizm olsun.

297
00:14:01,360 --> 00:14:03,350
Biz hala var
contiguousness Ben iddia ediyorum.

298
00:14:03,350 --> 00:14:05,881
Malloc bize verecektir çünkü
bellek bitişik bir yığın.

299
00:14:05,881 --> 00:14:08,630
Ama bu bir ağrı olacak
Bizim için boyun, programcı,

300
00:14:08,630 --> 00:14:09,770
Aslında kadar kod.

301
00:14:09,770 --> 00:14:10,730
Bu sadece daha fazla iş var.

302
00:14:10,730 --> 00:14:13,930
Biz ne benzer kodu gerekir
Sadece bir an önce dışarı vurarak.

303
00:14:13,930 --> 00:14:16,120
Çok yapılabilir, ancak bu karmaşıklık ekler.

304
00:14:16,120 --> 00:14:19,520
Ve böylece geliştirici zamanı, programcı
Zaman başka kaynak

305
00:14:19,520 --> 00:14:22,520
Biz harcamak gerekir diye
biraz zaman yeni özellikler elde etmek.

306
00:14:22,520 --> 00:14:24,020
Ve sonra tabii ki bir kuyruk var.

307
00:14:24,020 --> 00:14:26,227
Biz bu girmeyeceğim
çok detaylı bir.

308
00:14:26,227 --> 00:14:27,560
Ama ruhu çok benzer.

309
00:14:27,560 --> 00:14:31,220
Ben bir kuyruk uygulamak ve olabilir
bunun karşılık gelen işlemleri,

310
00:14:31,220 --> 00:14:35,660
enqueue veya dequeue eklemek veya kaldırmak gibi,
o, bunu demenin bir yolu meraklısı

311
00:14:35,660 --> 00:14:38,100
enqueue ya dequeue, aşağıdaki gibi.

312
00:14:38,100 --> 00:14:41,170
Ben sadece kendime bir yapı verebilir
yine bir sayının dizi var,

313
00:14:41,170 --> 00:14:44,000
yine bir boyuta sahiptir,
ama neden şimdi ihtiyacım var

314
00:14:44,000 --> 00:14:46,940
Bir sıranın önünde takip etmek?

315
00:14:46,940 --> 00:14:50,630
Bilmem gerek yoktu
Benim yığının ön.

316
00:14:50,630 --> 00:14:53,570
Peki, eğer tekrar bir
queue-- sadece sabit atalım

317
00:14:53,570 --> 00:14:57,870
beş gibi sahip olarak kod
Burada potansiyel olarak tamsayılar.

318
00:14:57,870 --> 00:15:00,940
Yani bu, sıfır, bir, iki, üç, dört.

319
00:15:00,940 --> 00:15:03,430
Bu olacak
tekrar aradı numaralar.

320
00:15:03,430 --> 00:15:06,940
Ve bu boyutta çağrılır.

321
00:15:06,940 --> 00:15:10,056
>> Neden yeterli değil
Sadece boyutu var mı?

322
00:15:10,056 --> 00:15:11,680
Peki, üzerinde bu aynı numaraları basalım.

323
00:15:11,680 --> 00:15:14,220
Ben de kuyruğa veya itti pushed--.

324
00:15:14,220 --> 00:15:20,150
Şimdi o 50 enqueue ve edeceğiz
51 ve daha sonra 61 ve nokta nokta nokta.

325
00:15:20,150 --> 00:15:21,070
Yani enqueue var.

326
00:15:21,070 --> 00:15:23,176
Daha sonra 61, sonra 50, 51 kuyruğa.

327
00:15:23,176 --> 00:15:25,050
Ve bu aynı görünüyor
Bugüne kadar bir yığın,

328
00:15:25,050 --> 00:15:27,190
dışında ben tek değişiklik yapmak gerekiyor.

329
00:15:27,190 --> 00:15:33,680
Bu boyut güncellemeniz gerekir, bu yüzden gitmek
Şimdi üç, bir ila iki sıfırdan.

330
00:15:33,680 --> 00:15:35,760
Nasıl sıradan çıkarma mı?

331
00:15:35,760 --> 00:15:36,890
Ne Dequeue ile olur?

332
00:15:36,890 --> 00:15:41,950
Kim ilk önce bu liste dışı gelmelidir
Apple Store çizgi olur?

333
00:15:41,950 --> 00:15:42,780
Yani 50.

334
00:15:42,780 --> 00:15:44,700
Dolayısıyla bu tür yanıltıcıdır bu zamanı.

335
00:15:44,700 --> 00:15:47,880
Son kez Oysa o süper oldu
kolay, sadece, boyutu eksi birini yapmak

336
00:15:47,880 --> 00:15:51,440
Ben etkili benim dizinin sonuna olsun
sayılardır, bu 61 kaldırır.

337
00:15:51,440 --> 00:15:52,920
Ama 61 kaldırmak istemiyorum.

338
00:15:52,920 --> 00:15:55,030
Ben, 50 almak isteyen
05:00 am oldu

339
00:15:55,030 --> 00:15:56,790
için sıraya
Yeni iPhone veya etajer.

340
00:15:56,790 --> 00:16:01,200
Ve bu yüzden, 50 kurtulmak için
sadece sağ, bunu yapamaz?

341
00:16:01,200 --> 00:16:02,547
Ben 50 üzerinden geçebilir.

342
00:16:02,547 --> 00:16:04,380
Ama biz sadece biz dedi
çok anal olmak zorunda değilsiniz

343
00:16:04,380 --> 00:16:06,330
olarak çizebilir veya veri gizlemek için.

344
00:16:06,330 --> 00:16:08,090
Nerede olduğunu Biz sadece unutabilirsiniz.

345
00:16:08,090 --> 00:16:12,330
>> Ama şimdi benim boyutunu değiştirmek durumunda
İki, bu yeterli bilgi

346
00:16:12,330 --> 00:16:15,711
Benim kuyruğunda olup bitenleri bilmek ister misiniz?

347
00:16:15,711 --> 00:16:16,680
Pek sayılmaz.

348
00:16:16,680 --> 00:16:19,830
Benim büyüklüğü, iki gibi ama
Sıra nerede kaçta başlayacak,

349
00:16:19,830 --> 00:16:22,980
Özellikle ben hala varsa
Bellekte bu aynı numaralar.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Yani hatırlamamız gerekiyor
Şimdi ön nerede.

352
00:16:27,090 --> 00:16:29,630
Ve bu yüzden ben önerdiği gibi
Orada, biz sadece çağrıda edeceğiz

353
00:16:29,630 --> 00:16:33,729
Olan ilk N. ön,
değeri nedir olmalıydı?

354
00:16:33,729 --> 00:16:35,270
Sıfır, listenin sadece başlangıç.

355
00:16:35,270 --> 00:16:40,876
Ama şimdi sıra azaltma için
boyut, biz sadece ön artırmak.

356
00:16:40,876 --> 00:16:42,000
Şimdi, burada başka bir sorun var.

357
00:16:42,000 --> 00:16:43,030
Yani devam edin zamanlar.

358
00:16:43,030 --> 00:16:47,520
Bu sayısıdır varsayalım
gibi 121, 124, ve daha sonra, kahretsin

359
00:16:47,520 --> 00:16:48,610
Ben boş alan var.

360
00:16:48,610 --> 00:16:50,390
Ama ben değilim, bir dakika bekleyin.

361
00:16:50,390 --> 00:16:55,630
Hikayenin bu noktasında Yani,
boyut, bir, iki olduğunu varsayalım,

362
00:16:55,630 --> 00:17:00,370
üç, dört, böylece varsayalım
boyutu, açık biri, dört olduğu

363
00:17:00,370 --> 00:17:01,621
yani 51 ön olduğunu.

364
00:17:01,621 --> 00:17:04,329
Burada başka bir numara koymak istiyorum,
ancak, kahretsin, ben boş alan var.

365
00:17:04,329 --> 00:17:06,710
Ama doğru, gerçekten değilim?

366
00:17:06,710 --> 00:17:11,192
Ben biraz nereye koymak olabilir
171 gibi ek değer?

367
00:17:11,192 --> 00:17:13,400
Evet, I could sadece tür
Doğru, geri oraya gitmek?

368
00:17:13,400 --> 00:17:18,161
Ve sonra 50 üzerinden çapraz veya
Sadece 171 ile üzerine.

369
00:17:18,161 --> 00:17:20,410
Ve neden merak ediyorsanız
Bizim sayılar, yani rastgele var

370
00:17:20,410 --> 00:17:24,150
Bu sık bilgisayar alınır
CS50 sonra Harvard'da bilim dersleri.

371
00:17:24,150 --> 00:17:27,510
Ama bu iyi bir optimizasyon oldu,
şimdi çünkü uzay israf değilim.

372
00:17:27,510 --> 00:17:30,750
Hala hatırlamak zorunda
ne kadar büyük bu şey toplamıdır.

373
00:17:30,750 --> 00:17:31,500
Beş toplam bulunuyor.

374
00:17:31,500 --> 00:17:33,375
Çünkü ben .... istemiyorum
51 üzerine başlayın.

375
00:17:33,375 --> 00:17:36,260
Yani şimdi ben hala alanı dışında duyuyorum,
böylece aynı sorun daha önce olduğu gibi.

376
00:17:36,260 --> 00:17:39,140
Ama nasıl şimdi görebiliyorum
kodunuzda, muhtemelen

377
00:17:39,140 --> 00:17:41,910
biraz daha yazmak zorunda
karmaşıklığı gerçekleşmesi için.

378
00:17:41,910 --> 00:17:44,510
Ve aslında ne operatörü
C muhtemelen sağlar

379
00:17:44,510 --> 00:17:48,110
Eğer sihirli Bu daireselliği mı?

380
00:17:48,110 --> 00:17:50,160
Evet Modulo operatörü,
yüzde işareti.

381
00:17:50,160 --> 00:17:53,160
Yani bir sıraya hakkında tür serin ne
Biz çizim diziler tutmak bile

382
00:17:53,160 --> 00:17:56,520
Bu gibi düz çizgiler olarak, eğer
tür kıvrılması olarak bu konuda düşünmek

383
00:17:56,520 --> 00:18:00,341
etrafında bir çember olarak, sonra sadece
sezgisel bu tür zihinsel işleri

384
00:18:00,341 --> 00:18:01,590
Ben daha temiz biraz düşünmek.

385
00:18:01,590 --> 00:18:05,190
Hala uygulamak zorunda kalacak
kodunda bu zihinsel modeli.

386
00:18:05,190 --> 00:18:07,550
Bu yüzden değil o kadar da zor,
sonuçta, uygulama

387
00:18:07,550 --> 00:18:12,430
ama biz yine de oldukça, size-- kaybetmek
Bunu yapmazsak yeteneği yeniden boyutlandırmak için.

388
00:18:12,430 --> 00:18:15,310
>> Biz dizinin kurtulmak için, biz
Tek bir işaretçi ile değiştirin,

389
00:18:15,310 --> 00:18:20,010
ve sonra bir yerde benim kod ben var
Bir aslında hangi fonksiyonu oluşturacağına çağrı

390
00:18:20,010 --> 00:18:23,720
Dizi denilen numaralar?

391
00:18:23,720 --> 00:18:26,190
Malloc, veya benzeri bir
işlevi, tam.

392
00:18:26,190 --> 00:18:30,481
Yığınlar veya sıralarda Herhangi bir sorunuz.

393
00:18:30,481 --> 00:18:30,980
Evet?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
İyi soru.

396
00:18:34,240 --> 00:18:35,830
Ne Modulo burada kullanabilirsiniz.

397
00:18:35,830 --> 00:18:38,520
Yani genel olarak, kullanırken
mod, bunu yapacağını

398
00:18:38,520 --> 00:18:40,620
büyüklüğüne
Bütün veri yapısı.

399
00:18:40,620 --> 00:18:44,120
Yani bir şey beş veya kapasite, eğer gibi
o sürekli var, muhtemelen yer almaktadır.

400
00:18:44,120 --> 00:18:47,100
Ama modulo beş yapıyor
Muhtemelen, yeterli değildir

401
00:18:47,100 --> 00:18:51,380
Bilmemiz gereken, çünkü biz do
burada ya burada ya da burada etrafında sarın.

402
00:18:51,380 --> 00:18:54,160
Yani belki de sensin
dahil etmek istediğiniz gidiyoruz

403
00:18:54,160 --> 00:18:57,220
şey boyutu veya
yanı sıra ön değişken.

404
00:18:57,220 --> 00:19:00,140
Yani sadece bu nispeten var
basit aritmetik ifade,

405
00:19:00,140 --> 00:19:02,000
ama modulo anahtar bileşen olacaktır.

406
00:19:02,000 --> 00:19:03,330
>> Yani kısa film eğer sen.

407
00:19:03,330 --> 00:19:05,780
Bir animasyon bazı
Başka bir üniversitede millet

408
00:19:05,780 --> 00:19:08,060
biz ettik o araya
Bu tartışma için uyarladı.

409
00:19:08,060 --> 00:19:12,630
Jack öğrenme içerir
kuyruklar ve istatistikleri hakkında gerçekler.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FİLM: Bir zamanlar,
Jack adında bir adam vardı.

412
00:19:21,890 --> 00:19:25,330
O arkadaşlar geldi,
Jack bir püf noktası yoktu.

413
00:19:25,330 --> 00:19:28,220
Yani Jack konuşmak için gitti
En popüler adam biliyordu.

414
00:19:28,220 --> 00:19:30,920
O Lou gitti ve ben ne yapmalıyım, diye sordu?

415
00:19:30,920 --> 00:19:33,400
Lou onun arkadaşı olduğunu gördüm
Gerçekten sıkıntılı oldu.

416
00:19:33,400 --> 00:19:36,050
Peki, o sadece, başladı
Eğer giymiş konum nasıl bakmak.

417
00:19:36,050 --> 00:19:38,680
Eğer herhangi bir kıyafet yok mu
Farklı bir görünüme sahip?

418
00:19:38,680 --> 00:19:39,660
Evet, Jack dedi.

419
00:19:39,660 --> 00:19:40,840
Eminim.

420
00:19:40,840 --> 00:19:43,320
Evime gel ve
Ben bunları size göstereyim.

421
00:19:43,320 --> 00:19:44,550
Bu yüzden Jack'in gitti.

422
00:19:44,550 --> 00:19:47,520
Ve Jack Lou kutusunu gösterdi
Nerede o, bütün gömlek tuttu

423
00:19:47,520 --> 00:19:49,260
ve pantolonunun ve onun çorap.

424
00:19:49,260 --> 00:19:52,290
Lou görüyorum ki, dedi
bir yığın tüm giysi.

425
00:19:52,290 --> 00:19:54,870
Neden bazı giymiyorum
kez süre diğerleri?

426
00:19:54,870 --> 00:19:58,020
>> Jack, dedi de, ben
, giysi ve çorap çıkarmak

427
00:19:58,020 --> 00:20:00,780
Ben onları yıkamak ve koyun
Onları uzak kutusunda.

428
00:20:00,780 --> 00:20:03,210
Ardından bir sonraki geliyor
Sabah ve yukarı ben hop.

429
00:20:03,210 --> 00:20:06,380
Ben kutusuna gidin ve almak
kapalı üst elbiselerimi.

430
00:20:06,380 --> 00:20:09,070
Lou hızla gerçekleşen
Jack sorun.

431
00:20:09,070 --> 00:20:12,080
O, giysi, CD'ler tuttu
ve yığın kitap.

432
00:20:12,080 --> 00:20:14,420
O uzandı
bir şey okumak veya giymek,

433
00:20:14,420 --> 00:20:17,100
o üst kitap ya da iç çamaşırı seçerdim.

434
00:20:17,100 --> 00:20:19,500
Sonra o bitince, o
Hemen geri koymak istiyorum.

435
00:20:19,500 --> 00:20:21,970
Geri o yığının en üstüne, giderdim.

436
00:20:21,970 --> 00:20:24,460
Ben çözümü biliyorum,
muzaffer Loud söyledi.

437
00:20:24,460 --> 00:20:27,090
Sen öğrenmek gerekir
bir sıra kullanmaya başlayabilirsiniz.

438
00:20:27,090 --> 00:20:29,870
Lou Jack'in elbiselerini aldı ve
dolaba astı.

439
00:20:29,870 --> 00:20:32,710
Ve o boşaltılması ne zaman
kutu, o sadece attı.

440
00:20:32,710 --> 00:20:36,500
>> Sonra Jack sonunda şimdi, dedi
gün, soldaki elbiselerini koymak

441
00:20:36,500 --> 00:20:37,990
Onları uzak koyduğunuzda.

442
00:20:37,990 --> 00:20:41,300
Sonra yarın sabah sizi
elbiselerini almak, güneşi görmek için

443
00:20:41,300 --> 00:20:43,440
satırın sonuna sağa, üzerinde.

444
00:20:43,440 --> 00:20:44,880
Görmüyor musun? Lou dedi.

445
00:20:44,880 --> 00:20:46,370
O kadar güzel olacak.

446
00:20:46,370 --> 00:20:49,770
Bir kez şeyi giyeceğim
önce iki kez bir şey giymek.

447
00:20:49,770 --> 00:20:52,670
Ve sıralarında her şeyi ile
Onun klozet ve raf,

448
00:20:52,670 --> 00:20:55,160
Jack hissetmeye başladı
kendinden oldukça emin.

449
00:20:55,160 --> 00:20:59,720
Lou tüm sayesinde ve
onun harika kuyruk.

450
00:20:59,720 --> 00:21:01,220
KONUŞMACI 1: Tamam, sevimli.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Yani gerçekten Ne olup bittiğini
Şimdi başlık altında üzerinde?

453
00:21:10,080 --> 00:21:12,370
Biz işaretçiler olması,
Biz Malloc sahip olduğu,

454
00:21:12,370 --> 00:21:15,680
Biz oluşturma yeteneği var
kendimiz için hafıza parçaları

455
00:21:15,680 --> 00:21:16,344
dinamik.

456
00:21:16,344 --> 00:21:18,510
Yani bu bir resim biziz
geçen gün glimpsed.

457
00:21:18,510 --> 00:21:21,180
Biz gerçekten durmadı
Bunun üzerine, fakat bu resim

458
00:21:21,180 --> 00:21:24,180
altında bulunmaktadır devam
Şimdi haftadır kaput.

459
00:21:24,180 --> 00:21:27,050
Ve böylece bu sadece temsil
biz boğuldum bir dikdörtgen,

460
00:21:27,050 --> 00:21:28,180
Bilgisayarınızın belleği.

461
00:21:28,180 --> 00:21:31,850
Ve belki bilgisayarınız veya CS50
Kimlik, bellek ya da RAM gigabayt vardır

462
00:21:31,850 --> 00:21:33,050
ya da iki gigabayt veya dört.

463
00:21:33,050 --> 00:21:34,450
Bu gerçekten önemli değil.

464
00:21:34,450 --> 00:21:37,240
İşletim sisteminiz
Windows ya da Mac OS veya Linux,

465
00:21:37,240 --> 00:21:41,120
esasen programı veriyor
bu erişime sahip olduğunu düşünmek

466
00:21:41,120 --> 00:21:42,982
bütünü için
Bilgisayarınızın belleği

467
00:21:42,982 --> 00:21:45,440
hatta çalışıyor olabilir ama
Aynı anda birden çok program.

468
00:21:45,440 --> 00:21:46,990
Yani gerçekte, bu gerçekten işe yaramazsa.

469
00:21:46,990 --> 00:21:49,448
Ama bu bir yanılsama tür
tüm programlarınızı verildi.

470
00:21:49,448 --> 00:21:53,110
Yani eğer, bu RAM iki konser vardı
Bilgisayar düşünmek nasıl olduğunu.

471
00:21:53,110 --> 00:21:57,110
>> Şimdi tesadüfen, bunlardan biri
şeyler bellek bu segmentlerden biri

472
00:21:57,110 --> 00:21:58,350
Bir yığın denir.

473
00:21:58,350 --> 00:22:01,680
Ve gerçekten her zaman
bugüne kadar yazı kodu

474
00:22:01,680 --> 00:22:05,900
Aradığınız bir
örneğin main fonksiyon.

475
00:22:05,900 --> 00:22:08,410
Herhangi bir zaman var olduğunu hatırlayın
çizilmiş bilgisayarın bellek,

476
00:22:08,410 --> 00:22:10,640
Ben her zaman bir çeşit çizmek
Burada bir dikdörtgen yarısı

477
00:22:10,640 --> 00:22:12,520
ve konuşurken rahatsız etmeyin
Yukarıda ne hakkında.

478
00:22:12,520 --> 00:22:15,980
Ana çağrıldığında, ben iddia Çünkü
bellek bu şeridi olsun

479
00:22:15,980 --> 00:22:16,970
Burada iner.

480
00:22:16,970 --> 00:22:20,650
Ana Ve eğer bir fonksiyon denir
swap gibi, iyi takas buraya.

481
00:22:20,650 --> 00:22:23,720
Ve işte, çıkıyor
nerede biten ediyor.

482
00:22:23,720 --> 00:22:26,277
Bir yığın olarak adlandırılan şey
Bilgisayarınızın belleği içinde.

483
00:22:26,277 --> 00:22:28,360
Şimdi günün sonunda,
Bu sadece adresleri olduğunu.

484
00:22:28,360 --> 00:22:30,680
Bu, byte sıfır gibi
Bayt biri, bayt 2 milyar.

485
00:22:30,680 --> 00:22:33,130
Ama bu konuda düşünüyorsanız
Bu dikdörtgen nesne olarak,

486
00:22:33,130 --> 00:22:35,130
Tüm biz her yapıyoruz
kez biz bir fonksiyonudur diyoruz

487
00:22:35,130 --> 00:22:37,180
yeni bir bellek dilim katman.

488
00:22:37,180 --> 00:22:41,700
Bir dilim bu işlevi veriyorsun
Kendi bellek ile çalışmak.

489
00:22:41,700 --> 00:22:44,490
>> Ve bu önemli olduğunu şimdi hatırlamıyorum.

490
00:22:44,490 --> 00:22:46,400
Biz var çünkü eğer
swap gibi bir şey

491
00:22:46,400 --> 00:22:51,610
A ve B gibi iki yerel değişkenler
Biz bir ve iki gelenler değerleri değiştirmek

492
00:22:51,610 --> 00:22:55,130
İki ve biri hatırlama
takas döndüğünde o,

493
00:22:55,130 --> 00:22:58,330
Bu dilim sanki bulunuyor
bellek sadece gitti.

494
00:22:58,330 --> 00:23:00,080
Gerçekte, hala var
Orada adli.

495
00:23:00,080 --> 00:23:01,940
Ve bir şey aslında hâlâ orada.

496
00:23:01,940 --> 00:23:05,410
Ama kavramsal, o kadar var
gerçi tamamen gitti.

497
00:23:05,410 --> 00:23:10,910
Ve böylece, ana iş herhangi bilmiyor
Bu, bu takas fonksiyonu yapıldı

498
00:23:10,910 --> 00:23:14,890
aslında o geçti sürece
işaretçi veya başvuruya göre argümanları.

499
00:23:14,890 --> 00:23:17,790
Şimdi, temel çözüm
takas ile bu soruna

500
00:23:17,790 --> 00:23:19,970
adrese göre bir şeyler geçiyor.

501
00:23:19,970 --> 00:23:23,250
Ama çok, ne çıkıyor
o kısmı yukarıda devam

502
00:23:23,250 --> 00:23:26,330
dikdörtgenin tüm bu zaman
Henüz daha fazla bellek orada var.

503
00:23:26,330 --> 00:23:28,790
Ve ne zaman dinamik
bellek ayrılamadı,

504
00:23:28,790 --> 00:23:32,020
o getString, içinde olsun hangi
Biz CS50 senin için yapıyorum

505
00:23:32,020 --> 00:23:34,710
Kütüphane veya siz eğer
malloc arayıp sormak

506
00:23:34,710 --> 00:23:37,950
Bir yığın için işletim sistemi
Bellek, bu yığından gelmez.

507
00:23:37,950 --> 00:23:40,960
Başka bir yerden geliyor
Bilgisayarınızın belleğinde

508
00:23:40,960 --> 00:23:42,220
Bu yığın denir.

509
00:23:42,220 --> 00:23:43,430
Ve herhangi bir farklı değil.

510
00:23:43,430 --> 00:23:44,285
Aynı RAM bulunuyor.

511
00:23:44,285 --> 00:23:45,160
Aynı bellek bulunuyor.

512
00:23:45,160 --> 00:23:49,080
Bu kalmış sadece RAM bulunuyor
Orada yerine buraya.

513
00:23:49,080 --> 00:23:50,750
>> Ve böylece bu ne anlama geliyor?

514
00:23:50,750 --> 00:23:53,650
Peki, bilgisayarınız varsa
bellek sınırlı miktarda

515
00:23:53,650 --> 00:23:57,450
ve yığın yüzden büyüyor
konuşan ve yığın, uygun için

516
00:23:57,450 --> 00:23:59,349
Bu ok, aşağı büyüyor.

517
00:23:59,349 --> 00:24:01,140
Diğer bir deyişle, her bir
zaman malloc diyoruz,

518
00:24:01,140 --> 00:24:03,430
Eğer bir dilim verilen konum
bellek, yukandan

519
00:24:03,430 --> 00:24:06,630
Biraz sonra, alt sonra belki biraz
alt, sen malloc çağrı her zaman,

520
00:24:06,630 --> 00:24:10,100
Yığın, bu kullanım var,
tür büyüyor,

521
00:24:10,100 --> 00:24:11,950
Neye yakın ve daha yakın büyüyen?

522
00:24:11,950 --> 00:24:13,382
Yığını.

523
00:24:13,382 --> 00:24:14,840
Yani bu iyi bir fikir gibi görünüyor?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Gerçekten net değil nerede Yani,
başka ne sen sadece yapabileceği

526
00:24:22,140 --> 00:24:23,910
bellek sınırlı bir miktarda var.

527
00:24:23,910 --> 00:24:25,200
Ama bu kesinlikle kötü.

528
00:24:25,200 --> 00:24:27,920
Bu iki okları vardır
birbirlerine kursu çökmesine.

529
00:24:27,920 --> 00:24:31,930
>> Ve o kadar da kötü adamı, millet çıkıyor
, programlama ile özellikle iyi

530
00:24:31,930 --> 00:24:36,140
ve bilgisayar hacklemek için çalışıyor,
Bu gerçeği yararlanabilir.

531
00:24:36,140 --> 00:24:38,290
Aslında, en düşünelim
Biraz pasajı.

532
00:24:38,290 --> 00:24:41,350
Yani bu okuyabilirsiniz bir örnektir
hakkında Wikipedia'da daha ayrıntılı.

533
00:24:41,350 --> 00:24:43,100
Biz sizi işaret edeceğiz
makale, eğer meraklı.

534
00:24:43,100 --> 00:24:45,650
Ama bir saldırı genellikle var
arabellek taşması olarak bilinen

535
00:24:45,650 --> 00:24:49,570
İnsanlarda olduğunca uzun süre varlığını sürdüren
işlemek için yeteneği vardı

536
00:24:49,570 --> 00:24:53,120
Özellikle C. bilgisayarın bellek,
Yani bu çok keyfi bir program,

537
00:24:53,120 --> 00:24:55,130
ama en aşağıdan yukarıya onu okuyalım.

538
00:24:55,130 --> 00:24:57,650
Argc karakter yıldızı argv içine ana.

539
00:24:57,650 --> 00:24:59,830
Yani onu alır bir program
komut satırı argümanları.

540
00:24:59,830 --> 00:25:03,620
Ve tüm ana görünüşte çağrı yok
Bir fonksiyon, basitlik için F diyoruz.

541
00:25:03,620 --> 00:25:04,610
Ve ne geçer?

542
00:25:04,610 --> 00:25:05,490
Birinin argv.

543
00:25:05,490 --> 00:25:09,320
Yani F geçer ne olursa olsun
Kelime kullanıcı yazdığınız olduğunu

544
00:25:09,320 --> 00:25:11,500
sonra isteminde
Programın ismi hiç.

545
00:25:11,500 --> 00:25:15,730
O kadar Sezar veya Vigenere gibi hangi
Eğer argv yapıyorsun çağırmak olabilir.

546
00:25:15,730 --> 00:25:16,680
>> Peki F nedir?

547
00:25:16,680 --> 00:25:19,760
F bir dize alır
tamamen kendi argüman olarak,

548
00:25:19,760 --> 00:25:22,100
AKA bir karakter yıldızı, aynı
şey, bir dize olarak.

549
00:25:22,100 --> 00:25:24,920
Ve bu keyfi denir
Bu örnekte bar.

550
00:25:24,920 --> 00:25:27,710
Ve sonra karakter c 12,
Sadece meslekten olmayan şartlarını,

551
00:25:27,710 --> 00:25:31,750
Bizim için yapıyor Char c dirseği 12 nedir?

552
00:25:31,750 --> 00:25:33,440
Ne işe yarıyor?

553
00:25:33,440 --> 00:25:36,490
Özellikle, bellek ayırma
12 karakter için 12 bayt.

554
00:25:36,490 --> 00:25:36,990
Kesinlikle.

555
00:25:36,990 --> 00:25:40,000
Ve sonra son satırı, karıştırın ve
kopyalama, muhtemelen görmedim.

556
00:25:40,000 --> 00:25:43,360
Bu bir dize kopya
Amacı hayatında işlev

557
00:25:43,360 --> 00:25:48,160
ikinci argüman kopyalamak için
İlk argüman,

558
00:25:48,160 --> 00:25:51,190
ama sadece kadar
bayt belirli sayıda.

559
00:25:51,190 --> 00:25:53,860
Yani üçüncü argüman diyor
Kaç bayt kopyalamak gerekir?

560
00:25:53,860 --> 00:25:56,720
Çubuğun uzunluğu,
ne yazdığınız kullanıcı.

561
00:25:56,720 --> 00:25:59,320
Ve içerikleri
vardır, bu dizeyi bar

562
00:25:59,320 --> 00:26:02,330
belleğe kopyalanan C'de işaret

563
00:26:02,330 --> 00:26:04,060
>> Yani bu tür aptalca görünüyor ve öyle.

564
00:26:04,060 --> 00:26:06,300
Bu yapmacık bir örnek,
ama temsili var

565
00:26:06,300 --> 00:26:10,100
saldırı vektörlerinin bir sınıfın,
Bir program saldıran bir yol.

566
00:26:10,100 --> 00:26:15,050
Tüm ince ve kullanıcı eğer iyi
11 karakter var bir kelime türleri

567
00:26:15,050 --> 00:26:18,040
Daha az artı ters eğik çizgi sıfır veya.

568
00:26:18,040 --> 00:26:22,830
Ne daha kullanıcı tipleri fazla ise
11 ya da 12 ya da 20 ya da 50 karakter?

569
00:26:22,830 --> 00:26:25,090
Yapacak bu program nedir?

570
00:26:25,090 --> 00:26:29,360
Potansiyel seg arıza. Gidiyor
körü körüne kadar barda her şeyi kopyalamak için

571
00:26:29,360 --> 00:26:31,750
olan uzunluğu için
kelimenin tam anlamıyla barda her şey

572
00:26:31,750 --> 00:26:36,307
adresine C Fakat C işaret
Sadece preemptively 12 byte olarak vermiştir.

573
00:26:36,307 --> 00:26:37,640
Ama hiçbir ek çek var.

574
00:26:37,640 --> 00:26:38,700
Koşullar olursa yok.

575
00:26:38,700 --> 00:26:40,580
Burada kontrol hiçbir hata yok.

576
00:26:40,580 --> 00:26:43,270
>> Ve böylece bu program nedir
yapacaksın sadece körü körüne bir

577
00:26:43,270 --> 00:26:45,750
diğer bir şey kopyalayın.

578
00:26:45,750 --> 00:26:47,880
Ve böylece bu çizerseniz
bir resim olarak, burada

579
00:26:47,880 --> 00:26:49,860
hafıza alanının sadece bir şerit.

580
00:26:49,860 --> 00:26:53,470
Yani biz, altta fark
Yerel değişken bar var.

581
00:26:53,470 --> 00:26:57,330
Store-- gidiyor o yüzden işaretçi
olduğunu, yerel argüman yerine

582
00:26:57,330 --> 00:26:58,672
Dize çubuğunu saklamak için gidiyoruz.

583
00:26:58,672 --> 00:27:00,380
Ve sonra sadece fark
Yukarıda bir istif halinde,

584
00:27:00,380 --> 00:27:02,505
Çünkü sormak her zaman
yığını bellek,

585
00:27:02,505 --> 00:27:04,310
o biraz gider
resimsel üstünde,

586
00:27:04,310 --> 00:27:06,270
Biz orada 12 bayt var haber.

587
00:27:06,270 --> 00:27:10,690
Sol üst bir adet C dirseği sıfır ve bir
Sağ alt bir adet C braket 11 olduğunu.

588
00:27:10,690 --> 00:27:12,870
Bu sadece nasıl bilgisayarlar var
Bunu ortaya koymak için gidiyor.

589
00:27:12,870 --> 00:27:18,300
Yani sadece sezgisel, bar daha varsa
olmak üzere toplam 12 karakter daha

590
00:27:18,300 --> 00:27:25,790
olan ters bölü sıfır,
12 veya C dirseği 12 gidecek?

591
00:27:25,790 --> 00:27:28,440
Ya da daha doğrusu nerede olduğunu 12.
karakter veya karakter 13th,

592
00:27:28,440 --> 00:27:30,900
gidiş yüzüncü karakter
resimde sonuna kadar?

593
00:27:30,900 --> 00:27:33,400
Üstünde veya altında?

594
00:27:33,400 --> 00:27:36,300
>> Doğru, çünkü rağmen
Yığın kendisi yukarı büyür

595
00:27:36,300 --> 00:27:39,590
Eğer bir şeyler koyduk kez
Bu, bu tasarım sebebiyle

596
00:27:39,590 --> 00:27:41,294
üstten alta doğru bellek koyar.

597
00:27:41,294 --> 00:27:44,460
Eğer fazla 12 bayt var eğer öyleyse,
Eğer çubuğu üzerine başlamak için gidiyoruz.

598
00:27:44,460 --> 00:27:47,280
Şimdi bu bir hata, ama var
gerçekten büyük bir anlaşma.

599
00:27:47,280 --> 00:27:51,130
Var çünkü Ama bu büyük bir anlaşma olduğunu
bellekte oluyor daha fazla şeyler.

600
00:27:51,130 --> 00:27:53,074
Yani burada nasıl olabilir var
açık olması, merhaba koydu.

601
00:27:53,074 --> 00:27:54,490
Ben isteminde Merhaba yazdıysanız.

602
00:27:54,490 --> 00:27:59,330
'H-E-L-L-O eğik sıfır, içinde biter
Bu 12 byte ve biz süper güvendeyiz.

603
00:27:59,330 --> 00:28:00,330
Herşey iyi.

604
00:28:00,330 --> 00:28:03,020
Ama bir şey yazarsanız
Artık, potansiyel olarak var

605
00:28:03,020 --> 00:28:05,860
bar uzaya sürünmeye gidiyor.

606
00:28:05,860 --> 00:28:08,405
Ama daha kötüsü, bu döner
Bütün bu zaman aşımı,

607
00:28:08,405 --> 00:28:11,530
konuştuğumuz hiç olsa bile
bu, yığın diğer şeyler için kullanılır.

608
00:28:11,530 --> 00:28:13,560
Bu sadece yerel değişkenler değil.

609
00:28:13,560 --> 00:28:15,100
>> C çok düşük seviyeli bir dildir.

610
00:28:15,100 --> 00:28:17,810
Ve bu tür gizlice
Ayrıca yığın kullanır

611
00:28:17,810 --> 00:28:21,260
ne zaman hatırlamak
işlevi ne denir

612
00:28:21,260 --> 00:28:26,040
adres, önceki fonksiyonun olduğunu
bu yüzden tekrar o işleve atlayabilirsiniz.

613
00:28:26,040 --> 00:28:29,980
Yani ana çağrılar arasında, takas zaman
şeyler yığını itti

614
00:28:29,980 --> 00:28:34,380
sadece, yerel değişkenler swapları değil
ya da argümanları, aynı zamanda gizlice itti

615
00:28:34,380 --> 00:28:37,510
yığın üzerine temsil edilen
Burada kırmızı dilim tarafından,

616
00:28:37,510 --> 00:28:40,520
Ana adresi fiziksel olarak
Bilgisayarınızın belleğinde,

617
00:28:40,520 --> 00:28:44,180
böylece değiştirilebilir yapılır, bilgisayar
Ben ana geri gitmek gerekir bilir

618
00:28:44,180 --> 00:28:46,760
ve ana işlevi yürütme bitirmek.

619
00:28:46,760 --> 00:28:51,960
Yani bu, şimdi tehlikeli çünkü eğer
merhaba daha iyi daha fazla kullanıcı tipleri,

620
00:28:51,960 --> 00:28:57,030
kullanıcının giriş clobbers şekilde
ya da, kırmızı bölüme yazar

621
00:28:57,030 --> 00:28:59,820
mantıklı eğer bilgisayarın
sadece körü körüne kabul edeceğim

622
00:28:59,820 --> 00:29:03,830
kırmızı dilim bayt olduğunu
o dönmelidir hangi adresi

623
00:29:03,830 --> 00:29:09,020
düşman ne ise yeterince akıllı ya da
bayt dizisi koymak için şanslı

624
00:29:09,020 --> 00:29:13,450
Orada bir adres gibi görünüyor,
ancak kod adresi var

625
00:29:13,450 --> 00:29:18,730
o bilgisayarı istediği
yerine main yürütmek için?

626
00:29:18,730 --> 00:29:21,670
>> Diğer bir deyişle, ne olursa
Kullanıcı, komut istemine yazıyor

627
00:29:21,670 --> 00:29:23,850
Sadece bir şey değil
Merhaba zararsız gibi

628
00:29:23,850 --> 00:29:28,210
ama eşdeğer kod aslında
Bütün bu kullanıcının dosyaları silmek için?

629
00:29:28,210 --> 00:29:30,060
Ya da bana kendi şifresini e-posta?

630
00:29:30,060 --> 00:29:31,940
Ya da oturum başlatmak onların
tuş vuruşlarını, değil mi?

631
00:29:31,940 --> 00:29:34,920
Bir yolu var, en Bugün şart edelim
Onlar merhaba sadece yazın ki

632
00:29:34,920 --> 00:29:36,711
Dünya ya ad,
onlar aslında olabilir

633
00:29:36,711 --> 00:29:39,570
Kod, sıfır geçmek ve
olanlar, bu bilgisayar

634
00:29:39,570 --> 00:29:43,450
kod ve bir adres hem de hatalar.

635
00:29:43,450 --> 00:29:48,950
Olsa Yani biraz soyut, eğer
Yeterince düşmanca kod kullanıcı türleri

636
00:29:48,950 --> 00:29:52,330
Burada olduğu gibi genelleme edeceğiz
A. A krizi veya düşmanlar olduğunu.

637
00:29:52,330 --> 00:29:53,140
Yani sadece kötü şeyler.

638
00:29:53,140 --> 00:29:55,306
Biz umurumda değil
sayılar ya da sıfır ya da olanları

639
00:29:55,306 --> 00:29:59,470
Bugün, bu tür sonuna kadar bu
kırmızı bölümü üzerine,

640
00:29:59,470 --> 00:30:01,580
bayt bu sekansı edin.

641
00:30:01,580 --> 00:30:05,020
O 835 C sıfır sekiz sıfır.

642
00:30:05,020 --> 00:30:08,960
Ve şimdi burada Wikipedia'nın makale olarak
Şimdi aslında başlarsanız, önerdi

643
00:30:08,960 --> 00:30:12,460
Bilgisayarınız yıllarda bayt etiketleme
Bellek, Wikipedia makalesi nedir

644
00:30:12,460 --> 00:30:19,060
önerdi, bu ne adres ise
O sol üst byte 80 C 0 3508 olduğunu.

645
00:30:19,060 --> 00:30:22,200
>> Diğer bir deyişle, kötü biri ise,
onun koduyla yeterince akıllı

646
00:30:22,200 --> 00:30:26,650
Aslında burada bir numara koymak için o
kod adresine tekabül

647
00:30:26,650 --> 00:30:29,180
o enjekte
bilgisayarın içine, sen

648
00:30:29,180 --> 00:30:31,050
Bilgisayarı kandırmak olabilir
bir şey yapıyor içine.

649
00:30:31,050 --> 00:30:34,140
, Dosyalarını kaldırma e-posta
şeyler, senin trafik koklama,

650
00:30:34,140 --> 00:30:36,710
kelimenin tam anlamıyla bir şey olabilir
bilgisayara enjekte.

651
00:30:36,710 --> 00:30:39,220
Ve böylece bir bellek taşması
özünde saldırı

652
00:30:39,220 --> 00:30:43,530
sadece aptal, aptal
Dizinin ağır basan o

653
00:30:43,530 --> 00:30:45,840
onun sınırları kontrol yoktu.

654
00:30:45,840 --> 00:30:48,850
Ve bu süper tehlikeli ne
ve aynı zamanda süper güçlü

655
00:30:48,850 --> 00:30:52,560
C biz gerçekten var olduğunu
bellekte her yerde erişim.

656
00:30:52,560 --> 00:30:55,320
Bu bize kalmış, programcılar,
kim orijinal kod yazmak

657
00:30:55,320 --> 00:30:59,330
Herhangi bir lanetlemek uzunluğunu kontrol etmek
Biz manipüle ediyoruz diziler.

658
00:30:59,330 --> 00:31:00,750
Yani açık olmak, düzeltme nedir?

659
00:31:00,750 --> 00:31:03,190
Bu geri atarsanız
Kod, yapmamalıyım sadece

660
00:31:03,190 --> 00:31:08,000
çubuğun uzunluğunu değiştirmek ne
Başka bir kontrol edilmelidir?

661
00:31:08,000 --> 00:31:10,620
Başka ne için yapıyor olmalı
Tamamen bu saldırıyı engellemek?

662
00:31:10,620 --> 00:31:14,110
Ben sadece körü körüne söylemek istemiyorum
gibi birçok bayt kopya gerektiğini

663
00:31:14,110 --> 00:31:16,140
olarak çubuğun uzunluğudur.

664
00:31:16,140 --> 00:31:18,910
Ben kopya söylemek istiyorum
gibi birçok bayt bar olan

665
00:31:18,910 --> 00:31:24,090
tahsis kadar
Bellek ya da maksimum 12.

666
00:31:24,090 --> 00:31:27,450
Yani durum eğer çeşit gerekir
Bu çubuğun uzunluğunu kontrol yapar,

667
00:31:27,450 --> 00:31:32,800
ama 12, biz sadece zor kod aşarsa
Mümkün olan maksimum mesafe olarak 12.

668
00:31:32,800 --> 00:31:35,910
Aksi takdirde sözde tampon
taşma saldırısı olabilir.

669
00:31:35,910 --> 00:31:38,451
Bu slaytlar alt kısmında,
Daha fazla okumak için meraklı iseniz

670
00:31:38,451 --> 00:31:41,200
Gerçek orijinal makale
Eğer bir göz atın isterseniz.

671
00:31:41,200 --> 00:31:44,550
>> Ama şimdi, fiyatların arasında
yetersizlikler burada ödedi.

672
00:31:44,550 --> 00:31:46,680
Yani bu bir hızlı oldu
En düşük seviye göz nedir

673
00:31:46,680 --> 00:31:49,709
sorunlar biz şimdi ortaya çıkabilir
Bilgisayarın bellek erişimi vardır.

674
00:31:49,709 --> 00:31:51,750
Ama başka bir sorun, biz
Zaten Pazartesi günü tökezledi

675
00:31:51,750 --> 00:31:53,800
sadece verimsizlik oldu
Bağlantılı bir listenin.

676
00:31:53,800 --> 00:31:56,019
Biz geri doğrusal zaman vardır.

677
00:31:56,019 --> 00:31:57,560
Biz artık bitişik dizi var.

678
00:31:57,560 --> 00:31:58,980
Biz rastgele erişim yok.

679
00:31:58,980 --> 00:32:00,710
Biz köşeli ayraç notasyonu kullanamazsınız.

680
00:32:00,710 --> 00:32:04,590
Biz kelimenin tam anlamıyla bir while döngüsü kullanmak zorunda
gibi ben bir an önce yazmıştım.

681
00:32:04,590 --> 00:32:09,740
Ancak Pazartesi günü, elimizden iddia
verimlilik aleme geri sürüngen

682
00:32:09,740 --> 00:32:13,040
bir şeyi elde
logaritmik belki ya da en iyi yine,

683
00:32:13,040 --> 00:32:16,120
var hatta belki de bir şey
sabit zaman sözde.

684
00:32:16,120 --> 00:32:19,840
Yani biz bu yeni kullanarak nasıl yapabilirim
araçlar, bu adresler, bu işaretçiler,

685
00:32:19,840 --> 00:32:22,210
ve bizim kendi şeyleri parçacığı?

686
00:32:22,210 --> 00:32:23,960
Peki, varsayalım
Burada bu bir demet

687
00:32:23,960 --> 00:32:27,170
Biz saklamak istediğiniz sayıların
verimli veri yapısı ve arama.

688
00:32:27,170 --> 00:32:30,960
Biz kesinlikle haftaya sarabilirsiniz
İki, bir diziye bu atmak

689
00:32:30,960 --> 00:32:33,150
ve ikili arama kullanarak arama yapın.

690
00:32:33,150 --> 00:32:34,040
Bölmek ve fethetmek.

691
00:32:34,040 --> 00:32:37,720
Ve aslında yazdığın
PSET3 ikili arama,

692
00:32:37,720 --> 00:32:40,100
nereye bulmak programı uyguladı.

693
00:32:40,100 --> 00:32:40,890
Ama biliyorum.

694
00:32:40,890 --> 00:32:45,060
Daha tür var
Bunu yapmanın akılcı bir yoldur.

695
00:32:45,060 --> 00:32:47,390
Biraz daha var
Sofistike ve belki de

696
00:32:47,390 --> 00:32:50,830
Bize neden ikili görmenizi sağlar
Arama çok daha hızlı böyledir.

697
00:32:50,830 --> 00:32:52,980
İlk olarak, tanıştırayım
Bir ağacın kavramı.

698
00:32:52,980 --> 00:32:54,730
Hangi bile olsa
gerçeklik ağaçları tür

699
00:32:54,730 --> 00:32:57,730
bilgisayar dünyasında, böyle büyüyecek
onlar tür aşağı büyümek bilim

700
00:32:57,730 --> 00:33:00,830
Eğer varsa bir aile ağacı gibi
dedesi veya büyük dedesi

701
00:33:00,830 --> 00:33:04,580
veya etajer üst, patrik olarak ve
ailenin aile, sadece bir

702
00:33:04,580 --> 00:33:07,930
Kök, düğüm aşağıda denilen
onun çocukları olan vardır,

703
00:33:07,930 --> 00:33:11,442
aşağıda onun çocuklarıdır ya
torunları daha genel olarak.

704
00:33:11,442 --> 00:33:13,400
Ve herkes asılı
etti alt

705
00:33:13,400 --> 00:33:16,070
ağaç, olmanın yanı sıra
Ailede genç,

706
00:33:16,070 --> 00:33:19,520
Ayrıca sadece jenerik olabilir
Ağacın yaprakları denir.

707
00:33:19,520 --> 00:33:21,800
>> Yani bu sadece bir demet
kelime ve tanımları

708
00:33:21,800 --> 00:33:25,790
bir şey için bilgisayarda bir ağaç olarak adlandırılan
bilim, bir aile ağacı gibi çok.

709
00:33:25,790 --> 00:33:28,770
Ama meraklısı enkarnasyonlarını var
ağaçların, bunlardan biri

710
00:33:28,770 --> 00:33:30,780
İkili arama ağacı denir.

711
00:33:30,780 --> 00:33:34,380
Ve yapabilirsiniz alay tür
Bu şey yapar ayrı şey.

712
00:33:34,380 --> 00:33:37,180
Peki, ne anlamda ikili değil mi?

713
00:33:37,180 --> 00:33:41,455
Nereden ikili buraya geliyor?

714
00:33:41,455 --> 00:33:41,955
Maalesef?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
O kadar çok bir ya da değil.

717
00:33:47,210 --> 00:33:52,000
Bu düğüm, her hayır vardır daha var
İkiden fazla çocuk, burada gördüğünüz gibi.

718
00:33:52,000 --> 00:33:54,990
Genel olarak, bir tree-- içinde ve
Ailen ve dedesi

719
00:33:54,990 --> 00:33:57,640
gibi birçok çocuk ya da
torun aslında istedikleri gibi,

720
00:33:57,640 --> 00:34:00,820
ve bu nedenle, örneğin orada biz üç var
O sağ düğümün kapalı çocuk,

721
00:34:00,820 --> 00:34:05,480
ancak bir ikili ağaç, bir düğüm vardır
maksimum, sıfır, bir ya da iki çocuk.

722
00:34:05,480 --> 00:34:08,496
Ve bu, güzel bir özellik var
ikisi tarafından kapatılmış oluyor çünkü eğer,

723
00:34:08,496 --> 00:34:10,620
Biz edebilmek için gidiyoruz
Biraz günlük tabanı olsun iki

724
00:34:10,620 --> 00:34:11,975
Eylem burada sonuçta oluyor.

725
00:34:11,975 --> 00:34:13,350
Bu yüzden logaritmik bir şey var.

726
00:34:13,350 --> 00:34:14,558
Ama bir anda bu konuda daha fazla.

727
00:34:14,558 --> 00:34:19,810
Arama ağaç numaraları anlamına gelir
düzenlenmiş öyle ki sol çocuğun

728
00:34:19,810 --> 00:34:22,429
değer kök büyüktür.

729
00:34:22,429 --> 00:34:26,010
Ve onun sağ çocuk
root daha büyük.

730
00:34:26,010 --> 00:34:29,290
Başka bir deyişle, herhangi alırsanız
düğümleri, bu resimdeki çevreler,

731
00:34:29,290 --> 00:34:31,840
ve solunda bakar
Çocuk ve sağ çocuk

732
00:34:31,840 --> 00:34:34,739
Birincisi, daha az olmalıdır
saniyeden daha büyük olmalıdır.

733
00:34:34,739 --> 00:34:36,159
Yani aklı 55 kontrol edin.

734
00:34:36,159 --> 00:34:37,780
Bu çocuğu kalan 33 olduğunu.

735
00:34:37,780 --> 00:34:38,620
O daha az.

736
00:34:38,620 --> 00:34:40,929
55, onun sağ alt 77'dir.

737
00:34:40,929 --> 00:34:41,783
Bu daha büyük bu.

738
00:34:41,783 --> 00:34:43,199
Ve bu özyinelemeli tanımı var.

739
00:34:43,199 --> 00:34:46,480
Biz onlardan her biri kontrol edebilir
düğümleri ve yapacağını aynı desen.

740
00:34:46,480 --> 00:34:49,389
>> Yani güzel ne
ikili arama ağacı olduğunu

741
00:34:49,389 --> 00:34:52,204
bu bir, biz bunu uygulayabilirsiniz
bir yapı ile, sadece bu gibi.

742
00:34:52,204 --> 00:34:54,620
Ve biz atıyorlar bile
AT yapıların sürü

743
00:34:54,620 --> 00:34:56,560
Bu veriler bir şekilde konum
Sezgisel şimdi umarım.

744
00:34:56,560 --> 00:35:00,570
Sözdizimi, hala emin esrarlı bir
ama bu bir düğümün içeriğini

745
00:35:00,570 --> 00:35:02,786
context-- ve biz tutmak
Kelime düğümünü kullanarak,

746
00:35:02,786 --> 00:35:04,910
Bir dikdörtgen olsun
ekran veya bir daire üzerinde,

747
00:35:04,910 --> 00:35:08,970
o, sadece bazı genel konteyner bulunuyor
gibi bir ağaç, bu durumda,

748
00:35:08,970 --> 00:35:11,780
biz bir tamsayı ihtiyacımız gördüm
düğümlerin her biri

749
00:35:11,780 --> 00:35:15,460
ve sonra ben iki işaretçileri işaret ihtiyaç
Sol çocuk ve sağ çocuğa,

750
00:35:15,460 --> 00:35:16,590
sırasıyla.

751
00:35:16,590 --> 00:35:20,730
Bu yüzden nasıl olabilir
bir yapı içinde olduğunu uygulamak.

752
00:35:20,730 --> 00:35:22,315
Ve nasıl kod uygulamak olabilir?

753
00:35:22,315 --> 00:35:26,730
Peki, hızlı atalım
Bu küçücük örnek bakmak.

754
00:35:26,730 --> 00:35:29,820
Bu işlevsel değil, ama var
Kopyalanan ve bu yapıyı yapıştırılan.

755
00:35:29,820 --> 00:35:33,510
Ve eğer bir ikili benim işlevi
arama ağacı, arama denir

756
00:35:33,510 --> 00:35:36,980
ve bu iki argüman alır,
bir tamsayı N ve bir işaretçi

757
00:35:36,980 --> 00:35:41,400
ağaç bir düğüm, yani bir işaretçi
veya bir ağacın köküne bir işaretçi,

758
00:35:41,400 --> 00:35:43,482
nasıl N ararken gidiyorsun?

759
00:35:43,482 --> 00:35:45,440
Peki, ilk, çünkü ben
işaretçileri ile ilgili,

760
00:35:45,440 --> 00:35:46,750
Ben bir sağlamlık denetimi yapmak için gidiyorum.

761
00:35:46,750 --> 00:35:54,279
Ağaç eşittir boş eşitse, N ise
Bu ağaçta ya da bu ağacın?

762
00:35:54,279 --> 00:35:55,070
Bu doğru olamaz?

763
00:35:55,070 --> 00:35:56,870
Ben boş geçmiş olsam,
Orada hiçbir şey yok.

764
00:35:56,870 --> 00:35:59,230
Ben belki de sadece
körü körüne return false söylüyorlar.

765
00:35:59,230 --> 00:36:04,050
Bana hiçbir şey verirsen, ben kesinlikle yapamam
herhangi bir sayı N. bulmak başka Yani ne olabilir

766
00:36:04,050 --> 00:36:04,750
şimdi kontrol et?

767
00:36:04,750 --> 00:36:12,830
Ben de başka bir N olup olmadığını söylemek için gidiyorum
Ağaç düğümünde ne olursa olsun daha az

768
00:36:12,830 --> 00:36:16,300
Ben N değerini teslim oldum.

769
00:36:16,300 --> 00:36:20,270
Diğer bir deyişle, sayısı eğer ben
N, arıyorum, düğümün daha az

770
00:36:20,270 --> 00:36:21,340
Ben bakıyorum söyledi.

771
00:36:21,340 --> 00:36:23,190
Ve düğüm Ben arıyorum
Ağaç denir de,

772
00:36:23,190 --> 00:36:26,370
ve önceki örnekte hatırlamak
bir işaretçi değeri almak için,

773
00:36:26,370 --> 00:36:28,310
Ben ok gösterimi kullanın.

774
00:36:28,310 --> 00:36:35,960
N ağacı ok daha az Yani
N, ben kavramsal sol gitmek istiyorum.

775
00:36:35,960 --> 00:36:38,590
Nasıl sol arıyor ekspres mı?

776
00:36:38,590 --> 00:36:41,560
Bu ise, açık olmak gerekirse
Söz konusu resim,

777
00:36:41,560 --> 00:36:44,612
ve ben geçti oldum üstteki olduğunu
aşağı işaret ediyor ok.

778
00:36:44,612 --> 00:36:45,570
Bu benim ağaç işaretçi var.

779
00:36:45,570 --> 00:36:48,060
Ben ağacın kökünde işaret ediyorum.

780
00:36:48,060 --> 00:36:52,100
Ve ben, diyelim arıyorum
keyfi sayı 44.

781
00:36:52,100 --> 00:36:55,300
Daha küçük veya 44
Açıkçası 55 daha büyük?

782
00:36:55,300 --> 00:36:56,360
Yani daha az.

783
00:36:56,360 --> 00:36:58,760
Ve böylece eğer bu durum geçerlidir.

784
00:36:58,760 --> 00:37:03,981
Yani kavramsal, ben ne istiyorum
Ben 44 arıyorum eğer sonraki arama?

785
00:37:03,981 --> 00:37:04,480
Evet?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Kesinlikle, ben istiyorum
Sol çocuğu arama

788
00:37:11,100 --> 00:37:12,789
ya bu resmin sol alt ağaç.

789
00:37:12,789 --> 00:37:14,830
Ve aslında, geçmeme izin
Buraya resim

790
00:37:14,830 --> 00:37:17,770
Sadece bir an için, çünkü
Ben bu kazımak olamaz.

791
00:37:17,770 --> 00:37:21,150
Ben 55 burada başlar ve varsa
Biliyorum bu değeri 44

792
00:37:21,150 --> 00:37:23,180
Için ben arıyorum
Sol, bu tür

793
00:37:23,180 --> 00:37:26,010
içinde telefon rehberini yırtarak gibi
Yarım veya yarıda ağaç yırtılma.

794
00:37:26,010 --> 00:37:29,660
Ben artık umurumda zorunda
Ağacın tüm bu yarısı.

795
00:37:29,660 --> 00:37:33,270
Ve yine, merakla açısından
yapı, burada üzerinde bu şey

796
00:37:33,270 --> 00:37:36,682
, 33 ile başlayan kendisi olduğunu
İkili arama ağacı.

797
00:37:36,682 --> 00:37:39,890
Çünkü daha önce kelime özyinelemeli dedi
Gerçekten de, bu bir veri yapısıdır olduğu

798
00:37:39,890 --> 00:37:41,707
tanımı gereği özyinelemeli olduğunu.

799
00:37:41,707 --> 00:37:44,540
Bunun olan bir ağaç olabilir
büyük, ama onun çocuklarının her biri

800
00:37:44,540 --> 00:37:46,870
küçük biraz bir ağacı temsil eder.

801
00:37:46,870 --> 00:37:50,910
Bunun yerine büyükbaba olmak
ya da büyükanne, şimdi sadece anne

802
00:37:50,910 --> 00:37:54,300
yoksa-- ben anne değil say-- olamaz
ya da baba, bu garip olurdu.

803
00:37:54,300 --> 00:37:59,000
Orada yerine iki çocuk
kardeşi ve kardeş gibi olurdu.

804
00:37:59,000 --> 00:38:01,120
Aile ağacı yeni nesil.

805
00:38:01,120 --> 00:38:02,900
Ama yapısal, aynı fikir.

806
00:38:02,900 --> 00:38:06,790
Ve ben bir işlevi var çıkıyor
hangi ile ben bir ikili arama arama yapabilirsiniz

807
00:38:06,790 --> 00:38:07,290
ağaç.

808
00:38:07,290 --> 00:38:08,680
Bu arama denir.

809
00:38:08,680 --> 00:38:17,870
Ben ağaç ok sol N arama
N değerinden büyükse else if

810
00:38:17,870 --> 00:38:18,870
ben şu anda değilim.

811
00:38:18,870 --> 00:38:20,800
Bir an önce hikaye 55.

812
00:38:20,800 --> 00:38:23,780
Ben adında bir işlevi var
arama ben sadece can

813
00:38:23,780 --> 00:38:29,660
N bu geçmek ve özyinelemeli arama
alt ağacı ve adil dönüş

814
00:38:29,660 --> 00:38:30,620
ne olursa olsun cevap.

815
00:38:30,620 --> 00:38:33,530
Else Burada bazı nihai taban dava var.

816
00:38:33,530 --> 00:38:35,310
>> Son durum nedir?

817
00:38:35,310 --> 00:38:36,570
Ağaç ya null.

818
00:38:36,570 --> 00:38:39,980
Ben de arıyorum değeri
bundan daha az ya da daha fazla

819
00:38:39,980 --> 00:38:42,610
ya da eşit.

820
00:38:42,610 --> 00:38:44,750
Ve ben eşit söyleyebiliriz
eşit, ancak mantıksal olarak bu kadar

821
00:38:44,750 --> 00:38:46,500
Sadece burada başka söyleyerek eşdeğer.

822
00:38:46,500 --> 00:38:49,150
Yani gerçek bir şey bulmak nasıl olduğunu.

823
00:38:49,150 --> 00:38:51,710
Yani umarım bu bir olduğunu
daha zorlayıcı bir örnek

824
00:38:51,710 --> 00:38:54,900
Aptal sigma fonksiyonu daha
Biz bir kaç dersler yaptım

825
00:38:54,900 --> 00:38:58,360
nerede bir döngü kullanımı gibi kolay
birinden bütün numaralarını saymak

826
00:38:58,360 --> 00:39:02,390
Bir veri yapısı ile Burada N'ye
kendisi, yinelemeli olduğu

827
00:39:02,390 --> 00:39:07,050
biz şimdi, tanımlanmış ve özyinelemeli çizilmiş
kendimizi ifade yeteneğine sahip

828
00:39:07,050 --> 00:39:09,780
kod kendisi özyinelemeli olduğunu.

829
00:39:09,780 --> 00:39:12,580
Yani bu burada aynı kodudur.

830
00:39:12,580 --> 00:39:14,400
>> Yani biz ne diğer sorunlar çözebilir?

831
00:39:14,400 --> 00:39:18,160
Uzağa Yani hızlı bir adım
Sadece bir an için ağaçlar.

832
00:39:18,160 --> 00:39:20,130
İşte isimli, Alman bayrağı söylüyorlar.

833
00:39:20,130 --> 00:39:22,020
Ve açıkça orada bir
Bu bayrak desen.

834
00:39:22,020 --> 00:39:23,811
Ve bir sürü var
Dünyada bayraklar o

835
00:39:23,811 --> 00:39:27,560
açısından bu kadar basit
Onların renk ve desen.

836
00:39:27,560 --> 00:39:31,930
Ama bu olarak saklanır varsayalım
.GIF Veya JPEG veya bitmap veya ping,

837
00:39:31,930 --> 00:39:34,240
herhangi bir grafik dosyası biçimi
hangi ile, aşina

838
00:39:34,240 --> 00:39:36,460
Biz konum bazıları
PSET4 içinde oynamaktan.

839
00:39:36,460 --> 00:39:41,550
Bu saklamak için değerli görünmüyor
siyah piksel, siyah piksel, siyah piksel,

840
00:39:41,550 --> 00:39:44,790
nokta, nokta, nokta, bir sürü
İlk scanline siyah pikseller,

841
00:39:44,790 --> 00:39:47,430
veya satır, daha sonra bir sürü
Aynı sonra bir sürü

842
00:39:47,430 --> 00:39:49,530
Daha sonra, aynı, ve
Kırmızı piksel sürü,

843
00:39:49,530 --> 00:39:53,020
kırmızı piksel, kırmızı piksel, daha sonra bir bütün
Sarı sarı piksel demet, değil mi?

844
00:39:53,020 --> 00:39:55,050
>> Böyle verimsizlik var burada.

845
00:39:55,050 --> 00:39:59,040
Nasıl sezgisel olur
Alman bayrağı sıkıştırmak

846
00:39:59,040 --> 00:40:01,320
Bir dosya olarak uygulanması durumunda?

847
00:40:01,320 --> 00:40:04,940
Hangi bilgileri gibi biz yapamam
sırayla diskte saklamak rahatsız

848
00:40:04,940 --> 00:40:08,040
gibi bizim dosya boyutunu azaltmak için
Bir kilobayt, bir şey, bir megabayt

849
00:40:08,040 --> 00:40:09,430
Daha küçük?

850
00:40:09,430 --> 00:40:13,130
Buradaki fazlalık yatıyor
Burada açık olması?

851
00:40:13,130 --> 00:40:13,880
Ne yapabilirdi?

852
00:40:13,880 --> 00:40:14,380
Evet?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Kesinlikle.

855
00:40:21,970 --> 00:40:24,550
Neden yerine hatırlıyorum
Her lanetlemek pikselin rengi

856
00:40:24,550 --> 00:40:28,200
sadece PSET4 içinde yapıyoruz gibi
Bitmap dosya formatı ile,

857
00:40:28,200 --> 00:40:32,060
neden sadece temsil etmemektedir
Örneğin piksel soldaki sütun,

858
00:40:32,060 --> 00:40:35,370
siyah pikseller bir demet, bir demet
kırmızı, sarı ve bir demet,

859
00:40:35,370 --> 00:40:39,210
ve sonra sadece her nasılsa kodlamak
tekrar fikri bu 100 kez

860
00:40:39,210 --> 00:40:41,020
ya bu 1000 kez tekrarlayın?

861
00:40:41,020 --> 00:40:43,430
Nerede 100 veya 1.000
Sadece bir tamsayı, sana bu yüzden

862
00:40:43,430 --> 00:40:47,290
sadece tek bir numara ile kurtulabiliriz
Bunun yerine yüzlerce ya da binlerce

863
00:40:47,290 --> 00:40:48,270
ek piksel.

864
00:40:48,270 --> 00:40:50,990
Ve gerçekten de, bu nasıl biz var
Alman bayrağı sıkıştırmak olabilir.

865
00:40:50,990 --> 00:40:51,490
Ve

866
00:40:51,490 --> 00:40:53,470
Fransız bayrağı hakkında şimdi ne olacak?

867
00:40:53,470 --> 00:40:58,930
Bazı tür ve biraz
zihinsel egzersiz, hangi bayrak

868
00:40:58,930 --> 00:41:01,040
diskte daha fazla sıkıştırılmış olabilir?

869
00:41:01,040 --> 00:41:05,720
Alman bayrağı veya Fransızca
bayrak, biz bu yaklaşım olur?

870
00:41:05,720 --> 00:41:08,490
Alman bayrağı, var, çünkü
daha yatay fazlalık.

871
00:41:08,490 --> 00:41:12,190
Ve tasarım, çok sayıda grafik dosya
biçimleri gerçekten de tarama çizgileri çalışır

872
00:41:12,190 --> 00:41:12,830
yatay.

873
00:41:12,830 --> 00:41:14,674
Onlar işe yarayabilir
dikey, sadece insanlık

874
00:41:14,674 --> 00:41:17,090
karar yıl önce yaparız
Genellikle işler satır düşünüyorum

875
00:41:17,090 --> 00:41:18,880
kolonu ile satır yerine kolonu ile.

876
00:41:18,880 --> 00:41:20,820
Yani gerçekten sen olsaydın
dosyaya bakmak için

877
00:41:20,820 --> 00:41:24,670
Bir Alman bayrağı ve Fransızca boyutu
bayrak, bu kadar uzun çözünürlüğü olarak

878
00:41:24,670 --> 00:41:27,530
Aynı, aynı genişlik
ve yükseklik bu

879
00:41:27,530 --> 00:41:31,580
Burada, daha büyük olacak çünkü sen
Kendinize üç kez tekrarlamak zorunda.

880
00:41:31,580 --> 00:41:35,570
Mavi, tekrarı belirtmek zorunda
Kendinizi, beyaz, kırmızı, kendinizi tekrar

881
00:41:35,570 --> 00:41:36,740
Kendinizi tekrarlayın.

882
00:41:36,740 --> 00:41:39,000
Sadece tüm gidemez
sağa yolu.

883
00:41:39,000 --> 00:41:41,200
Ve bir kenara olarak, yapmak
sıkıştırma temizlemek

884
00:41:41,200 --> 00:41:43,910
Bu ise, her yerde
Bir video-- dört çerçeveler

885
00:41:43,910 --> 00:41:45,890
Bir film olduğunu hatırlamak olabilir
ya da video genellikle

886
00:41:45,890 --> 00:41:47,286
saniyede 29 veya 30 kare gibi.

887
00:41:47,286 --> 00:41:50,410
Biraz flip kitap gibi nerede
Sadece görüntü, resim, görüntü, görüntüyü görmek,

888
00:41:50,410 --> 00:41:54,410
Görüntü sadece süper hızlı bu yüzden gibi görünüyor
Ekrandaki aktörlerin hareket ediyor.

889
00:41:54,410 --> 00:41:57,130
İşte arı üzerinde bulunuyor
bir demet çiçek üst.

890
00:41:57,130 --> 00:41:59,790
Ve bu tür olabilir ama
ilk bakışta görmek zor,

891
00:41:59,790 --> 00:42:04,020
hareket tek şey
Bu film arı olduğunu.

892
00:42:04,020 --> 00:42:06,880
>> Ne depolama hakkında aptal
Video sıkıştırılmamış?

893
00:42:06,880 --> 00:42:11,420
Bu Videoyu saklamak için bir atığın tür
Dört neredeyse aynı görüntü olarak o

894
00:42:11,420 --> 00:42:13,670
Sadece ölçüde arı olduğu kadar farklıdır.

895
00:42:13,670 --> 00:42:16,280
Sen uzağa atabilir çoğu
bu bilginin

896
00:42:16,280 --> 00:42:20,190
ve tek unutmayın, örneğin,
İlk kare ve son kare,

897
00:42:20,190 --> 00:42:22,180
Eğer yasiyorsaniz anahtar kare
Hiç, kelime duymadım

898
00:42:22,180 --> 00:42:24,337
ve sadece saklamak
arı olan orta.

899
00:42:24,337 --> 00:42:26,170
Ve gerek yok
, pembe tüm mağaza

900
00:42:26,170 --> 00:42:28,330
mavi ve ve
Yeşil değerler de.

901
00:42:28,330 --> 00:42:31,200
Yani bu sadece demek ki
sıkıştırma her yerde.

902
00:42:31,200 --> 00:42:34,900
Biz sık sık kullandığımız bir tekniktir
bu gün için verilen veya almak.

903
00:42:34,900 --> 00:42:38,750
>> Ama nasıl metin sıkıştırmak mı?

904
00:42:38,750 --> 00:42:40,450
Nasıl metnin sıkıştırılması gidiyorsun?

905
00:42:40,450 --> 00:42:45,410
Eh, karakterlerin her
ASCII bir byte veya sekiz bittir.

906
00:42:45,410 --> 00:42:47,360
Ve bu tür aptal, haklı?

907
00:42:47,360 --> 00:42:51,160
Muhtemelen A tipi nedeniyle
ve E ve ben ve O ve U çok

908
00:42:51,160 --> 00:42:55,270
daha sık W ya da Q ya da Z gibi daha
dile bağlı olan

909
00:42:55,270 --> 00:42:56,610
kesinlikle yazıyoruz.

910
00:42:56,610 --> 00:42:59,600
Ve böylece neden kullanıyorsunuz
Her harf için sekiz bit,

911
00:42:59,600 --> 00:43:02,040
En az olmak üzere
popüler mektuplar, değil mi?

912
00:43:02,040 --> 00:43:05,300
Neden için daha az bit kullanmak
süper popüler harfler,

913
00:43:05,300 --> 00:43:07,760
E gibi, şeyler sanırım
İlk Wheel of Fortune olarak,

914
00:43:07,760 --> 00:43:10,450
ve daha fazla bit kullanımı
az popüler mektuplar?

915
00:43:10,450 --> 00:43:10,950
Neden?

916
00:43:10,950 --> 00:43:13,130
Biz sadece gidiyoruz çünkü
daha az sıklıkla kullanıyorum.

917
00:43:13,130 --> 00:43:15,838
>> Peki, orada var olduğu ortaya çıkıyor
Bunu yapmak için yapılan girişimler olmuştur.

918
00:43:15,838 --> 00:43:18,630
Ve notu çağırmak durumunda
okul ya da lise, Mors kodu.

919
00:43:18,630 --> 00:43:20,400
Mors kodu noktalar var
ve çizgiler olabilir

920
00:43:20,400 --> 00:43:24,270
bir tel gibi boyunca iletilen
sesler ya da bir tür sinyaller.

921
00:43:24,270 --> 00:43:25,930
Ama Mors kodu süper temiz.

922
00:43:25,930 --> 00:43:29,010
Bu bir ikili sistemin tür
Bu sizi noktalar veya tire var.

923
00:43:29,010 --> 00:43:30,977
Ama, örneğin, iki nokta görürseniz.

924
00:43:30,977 --> 00:43:33,810
Ya da operatöre geri düşünüyorsanız
kim, bip, bip, bip sesi gibi gider

925
00:43:33,810 --> 00:43:36,760
bip biraz tetik isabet
bir sinyal gönderir,

926
00:43:36,760 --> 00:43:40,360
eğer alıcı, iki alır
noktalar ne mesaj aldınız?

927
00:43:40,360 --> 00:43:43,490
Tamamen keyfi.

928
00:43:43,490 --> 00:43:44,450
>> BEN?

929
00:43:44,450 --> 00:43:45,060
BEN?

930
00:43:45,060 --> 00:43:47,500
Ya da ne about-- ya da ben?

931
00:43:47,500 --> 00:43:49,570
Belki de sadece iki E'nin haklıydı?

932
00:43:49,570 --> 00:43:52,480
Yani bu sorun var
Morse ile decodability arasında

933
00:43:52,480 --> 00:43:54,890
Kod, bu sayede sürece
Size mesaj göndererek kişi

934
00:43:54,890 --> 00:43:59,510
aslında bunu size sıralayabilirsiniz duraklar
bakın veya harfler arasındaki boşlukları duymak,

935
00:43:59,510 --> 00:44:02,990
Sadece yeterli değil
sıfırlar ve olanları bir akışı göndermek,

936
00:44:02,990 --> 00:44:05,610
veya noktalar ve tire,
belirsizlik var çünkü.

937
00:44:05,610 --> 00:44:08,640
E bir tek nokta, bu yüzden eğer
İki nokta görmeniz ya da iki nokta duymak,

938
00:44:08,640 --> 00:44:11,254
belki de iki E'nin var ya da belki tek I. var

939
00:44:11,254 --> 00:44:13,670
Yani bir var bir sisteme ihtiyacımız var
Bundan daha zeki küçük.

940
00:44:13,670 --> 00:44:16,851
Yani bir erkek adında Huffman yıllar
önce tam olarak bu ile geldi.

941
00:44:16,851 --> 00:44:18,600
Yani biz sadece gidiyoruz
hızlı bir bakış almaya

942
00:44:18,600 --> 00:44:20,114
Nasıl ağaçlar bu germane bulunmaktadır.

943
00:44:20,114 --> 00:44:22,530
Bu, bazı olduğunu varsayalım
Göndermek istediğiniz aptal mesajı

944
00:44:22,530 --> 00:44:26,342
Sadece A, B oluşan C'nin D'nin ve E'nin,
ancak fazlalık Burada bir sürü var.

945
00:44:26,342 --> 00:44:27,550
Bu İngilizce olması gerekiyordu değil.

946
00:44:27,550 --> 00:44:28,341
Bu şifreli değil.

947
00:44:28,341 --> 00:44:30,540
Sadece aptal bir mesaj var
tekrar bir sürü ile.

948
00:44:30,540 --> 00:44:34,010
Aslında saymak Yani tüm
A takımından, B, C kıyafetleri, D'nin, ve E'nin, burada

949
00:44:34,010 --> 00:44:34,890
sıklığı.

950
00:44:34,890 --> 00:44:37,800
Harflerin% 20
Bir kıyafetleri, mektupları% 45

951
00:44:37,800 --> 00:44:39,660
E'nin, ve diğer üç frekansları vardır.

952
00:44:39,660 --> 00:44:41,960
Biz el orada sayılır
ve sadece matematik yaptım.

953
00:44:41,960 --> 00:44:44,579
>> Bu yüzden çıkıyor
Huffman, bir süre önce,

954
00:44:44,579 --> 00:44:46,620
bilirsin, fark
Ne ben binayı başlatırsanız

955
00:44:46,620 --> 00:44:51,172
Bir ağaç veya ağaçlar orman, eğer sen,
aşağıdaki gibi, ben aşağıdakileri yapabilirsiniz.

956
00:44:51,172 --> 00:44:53,880
Her bir düğüm vereceğim
Ben umurumda harflerin

957
00:44:53,880 --> 00:44:55,530
ve ben saklamak için gidiyorum
bu düğüm içinde

958
00:44:55,530 --> 00:44:58,610
Bir kayan nokta olarak frekansları
değer veya siz de bir N-ebil kullanma

959
00:44:58,610 --> 00:45:00,210
ama biz sadece burada bir şamandıra kullanacağız.

960
00:45:00,210 --> 00:45:03,100
Ve algoritma
o senin olduğunu önerdi

961
00:45:03,100 --> 00:45:07,210
tek bir düğüm bu ormanı almak
ağaçlar, bu yüzden süper kısa ağaçlar,

962
00:45:07,210 --> 00:45:11,920
ve onları bağlayan başlamak
yeni gruplar, yeni anne-babalar, eğer sen.

963
00:45:11,920 --> 00:45:16,150
Ve seçerek bunu
Bir anda iki küçük frekansları.

964
00:45:16,150 --> 00:45:18,110
Yani% 10 ve% 10 aldı.

965
00:45:18,110 --> 00:45:19,090
Ben yeni bir düğüm oluşturun.

966
00:45:19,090 --> 00:45:20,910
Ve ben yeni düğüm% 20 diyoruz.

967
00:45:20,910 --> 00:45:22,750
>> Hangi iki düğüm sonraki birleştirmek?

968
00:45:22,750 --> 00:45:23,810
Biraz belirsiz bu.

969
00:45:23,810 --> 00:45:26,643
Yani bazı köşe durumlarda var
düşünün, ama güzel şeyleri tutmak için,

970
00:45:26,643 --> 00:45:29,300
Ben% 20 seçmek için gidiyorum -
Ben şimdi çocukları görmezden.

971
00:45:29,300 --> 00:45:33,640
Ben% 20 seçmek için gidiyorum ve
% 15 ve iki yeni kenarlar çizin.

972
00:45:33,640 --> 00:45:35,624
Ve şimdi hangi iki düğüm
Ben mantıklı birleştirmek?

973
00:45:35,624 --> 00:45:38,540
Tüm çocukları, tüm Ignore
torunları, sadece köklerine bakmak

974
00:45:38,540 --> 00:45:39,070
şimdi.

975
00:45:39,070 --> 00:45:42,220
Hangi iki düğüm Birlikte kravat mı?

976
00:45:42,220 --> 00:45:44,530
İkinci nokta ve 0.35.

977
00:45:44,530 --> 00:45:45,890
Bu yüzden bana iki yeni kenarlar çizelim.

978
00:45:45,890 --> 00:45:47,570
Ve sonra ben yalnızca bir sol var.

979
00:45:47,570 --> 00:45:48,650
Yani burada bir ağaç.

980
00:45:48,650 --> 00:45:51,160
Ve kasten çizilmiş oldu
tür güzel bakmak,

981
00:45:51,160 --> 00:45:55,870
ama kenarları olduğunu fark
Ayrıca sıfır ve bir etiketlendi.

982
00:45:55,870 --> 00:45:59,510
Yani sol kenarları tümü sıfır
keyfi, ama sürekli.

983
00:45:59,510 --> 00:46:01,170
Tüm doğru kenarları olanlardır.

984
00:46:01,170 --> 00:46:05,070
>> Ve böylece Hoffman, isimli önerisi ile
Bir B temsil etmek istiyorsanız,

985
00:46:05,070 --> 00:46:10,080
Numarayı 66 temsil yerine
Sekiz tüm bit bir Ascii,

986
00:46:10,080 --> 00:46:13,360
ne sadece mağaza biliyorum
desen sıfır, sıfır, sıfır,

987
00:46:13,360 --> 00:46:17,030
Sıfır bu yolu var, çünkü
Benim ağacından Sayın Huffman ağacı,

988
00:46:17,030 --> 00:46:18,600
kökünden yaprak.

989
00:46:18,600 --> 00:46:20,970
Bir saklamak istiyorsanız
E, aksine, yapma

990
00:46:20,970 --> 00:46:26,290
Bir E. temsil eden sekiz bit göndermek
Bunun yerine, bit ne desen göndermek?

991
00:46:26,290 --> 00:46:26,890
Bir.

992
00:46:26,890 --> 00:46:30,410
Ve bu konuda güzel ne
Bu E en popüler mektup,

993
00:46:30,410 --> 00:46:32,340
ve kullandığınız
Bunun için en kısa kodu.

994
00:46:32,340 --> 00:46:34,090
Bir sonraki en popüler
mektup öyle görünüyor

995
00:46:34,090 --> 00:46:37,380
A. oldu Ve böylece kaç bit
o için kullanıyor teklif mi?

996
00:46:37,380 --> 00:46:38,270
Sıfır, bir.

997
00:46:38,270 --> 00:46:41,060
>> Ve bu uygulamaya çünkü
Bu ağaç gibi, şimdi

998
00:46:41,060 --> 00:46:43,350
Benim orada şart izin
Morse hiçbir belirsizlik

999
00:46:43,350 --> 00:46:46,090
kod, tüm çünkü
önemsediğiniz mektuplar

1000
00:46:46,090 --> 00:46:48,780
Bu kenarlarda sonundadır.

1001
00:46:48,780 --> 00:46:50,580
Yani bu sadece biri
Bir ağacın uygulaması.

1002
00:46:50,580 --> 00:46:52,538
Bu bu-- ve ben dalga edeceğiz
Bu benim eli nasıl

1003
00:46:52,538 --> 00:46:55,570
bir Cı-yapı olarak, bu uygulayabilir.

1004
00:46:55,570 --> 00:46:58,260
Biz sadece birleştirmek gerekiyor
Bir sembol, bir char gibi,

1005
00:46:58,260 --> 00:46:59,910
ve frekans sol ve sağ.

1006
00:46:59,910 --> 00:47:02,510
Ama iki bakalım
Son örnekler olacak

1007
00:47:02,510 --> 00:47:06,070
sonra oldukça tanıdık olsun
problem yarışması sıfır beş set.

1008
00:47:06,070 --> 00:47:09,210
>> Yani veri yapısı var
karma tablo olarak da bilinir.

1009
00:47:09,210 --> 00:47:12,247
Ve bir karma tablo tür bir
o kovalar sahip olması serin.

1010
00:47:12,247 --> 00:47:14,830
Ve dört kova var varsayalım
Burada, sadece dört boşluk.

1011
00:47:14,830 --> 00:47:20,830
İşte burada olduğu kartların bir güverte ve
Kulüp, kürek, kulüp, elmas, kulüp,

1012
00:47:20,830 --> 00:47:25,960
elmas, kulüp, elmas,
clubs-- nedenle bu rastgele.

1013
00:47:25,960 --> 00:47:30,330
Kalpler, hearts-- yüzden ben
Burada tüm giriş uçlarını bucketizing.

1014
00:47:30,330 --> 00:47:32,430
Ve bir karma tablo ihtiyaçları
senin girdi bakmak için,

1015
00:47:32,430 --> 00:47:34,850
ve daha sonra belli bir koyun
Gördüğünüz ne dayalı yerleştirin.

1016
00:47:34,850 --> 00:47:35,600
Bu bir algoritma var.

1017
00:47:35,600 --> 00:47:37,980
Ve ben bir süper kullanıyordum
Basit bir görsel algoritma.

1018
00:47:37,980 --> 00:47:40,030
En zor kısmı oldu
Resimler ne olduğunu hatırlayarak.

1019
00:47:40,030 --> 00:47:41,590
Ve sonra toplam dört şey var.

1020
00:47:41,590 --> 00:47:45,440
>> Şimdi yığınlar, büyüyen hangi
Burada kasıtlı tasarım şeydir.

1021
00:47:45,440 --> 00:47:46,540
Ama başka ne olabilir?

1022
00:47:46,540 --> 00:47:49,080
Yani aslında burada var bir
eski okul sınav kitaplarının demet.

1023
00:47:49,080 --> 00:47:51,240
Bir demet Varsayalım ki
Öğrenciler isimler burada bulunmaktadır.

1024
00:47:51,240 --> 00:47:52,570
İşte büyük bir karma tablo var.

1025
00:47:52,570 --> 00:47:54,867
Yerine dört kovalar,
Ben, en 26 diyelim var.

1026
00:47:54,867 --> 00:47:57,950
Ve biz 26 ödünç gitmek istemiyordu
dış [gelen şeyler? Annenberg?], Bu yüzden

1027
00:47:57,950 --> 00:48:00,289
Burada temsil beş var
A'dan Z'ye aracılığıyla Ve ben

1028
00:48:00,289 --> 00:48:03,580
, adı A ile başlayan bir öğrenci bakın
Orada onun ya da onu sınavı koymak için gidiyorum.

1029
00:48:03,580 --> 00:48:08,850
Birisi C başlarsa, orada,
A- aslında bunu yapmak istemiyordu.

1030
00:48:08,850 --> 00:48:10,060
B buraya gidiyor.

1031
00:48:10,060 --> 00:48:13,390
Yani var A ve B ve C Ve
şimdi burada başka bir öğrencisi.

1032
00:48:13,390 --> 00:48:16,212
Ama bu karma tablo ise
bir dizi ile uygulanan

1033
00:48:16,212 --> 00:48:17,920
Ben biraz berbat ediyorum
Bu noktada, doğru mu?

1034
00:48:17,920 --> 00:48:19,510
Ben biraz bu bir yere koymak gerekir.

1035
00:48:19,510 --> 00:48:24,380
>> Yani bu çözebilir tek yolu tüm olup
Doğru, A, C meşgul, B meşgul, meşgul.

1036
00:48:24,380 --> 00:48:28,880
Ben Yani D. onu koymak için gidiyorum
İlk, ben rastgele anında erişim var

1037
00:48:28,880 --> 00:48:31,064
Öğrenciler için kovalar her.

1038
00:48:31,064 --> 00:48:33,230
Ama şimdi bu tür intikal ediyor
şey doğrusal içine

1039
00:48:33,230 --> 00:48:36,750
Ben kimse için aramak istiyorsanız, çünkü
kimin adı A ile başlayan, ben burada kontrol edin.

1040
00:48:36,750 --> 00:48:38,854
Ancak bu bir değilse
Ben arıyorum, öğrenci,

1041
00:48:38,854 --> 00:48:41,520
Tür kontrol başlamak zorunda
kovalar, ben ne yaptım çünkü

1042
00:48:41,520 --> 00:48:44,530
arasında doğrusal sıralama oldu
veri yapısını soruşturma.

1043
00:48:44,530 --> 00:48:47,710
Sadece bakmak söyleyerek bir aptal yolu
İlk kullanılabilir açılması için,

1044
00:48:47,710 --> 00:48:51,850
ve, tabiri caizse, bir B planı olarak koymak
veya bu durumda planın D, değer

1045
00:48:51,850 --> 00:48:53,340
Bunun yerine bu konumda.

1046
00:48:53,340 --> 00:48:56,470
Bunun anlamı, yasiyorsaniz sadece bu yüzden olduğunu
26 yerleri ve hiçbir öğrencileri var

1047
00:48:56,470 --> 00:49:00,600
adı Q veya Z, falan gibi olan
Bu, en azından alanı kullanarak ediyoruz.

1048
00:49:00,600 --> 00:49:03,140
>> Ama biz zaten daha gördüm
Burada zeki çözümler, değil mi?

1049
00:49:03,140 --> 00:49:04,870
Bunun yerine ne yapardın
Eğer bir çarpışma varsa?

1050
00:49:04,870 --> 00:49:06,670
Iki kişi varsa,
adı A, ne istiyorsunuz

1051
00:49:06,670 --> 00:49:09,160
daha akıllı ya da daha fazla olmuştur
Sadece daha kolay çözüm

1052
00:49:09,160 --> 00:49:12,840
D olması gerekiyordu A koyarak?

1053
00:49:12,840 --> 00:49:14,810
Neden sadece gitmeyin
dış [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
malloc, başka bir düğüm gibi, koyun
Burada ve daha sonra burada bir öğrenci koymak.

1055
00:49:19,960 --> 00:49:22,120
I esas sahip böylece
Bir dizinin çeşit,

1056
00:49:22,120 --> 00:49:25,590
ya da konum olarak belki daha zarif
Bağlantılı bir listesini görmek için başlıyor.

1057
00:49:25,590 --> 00:49:29,520
>> Ve böylece bir karma tablo bir yapıdır
Bu, sadece bu gibi görünebilir

1058
00:49:29,520 --> 00:49:33,900
ama daha akıllıca, sen bir şey denir
Ayrı zincirleme, böylece bir karma tablo

1059
00:49:33,900 --> 00:49:38,340
oldukça sade bir dizi her biri olduğunu
olan elemanları bir sayı değil,

1060
00:49:38,340 --> 00:49:40,470
bağlantılı liste kendisidir.

1061
00:49:40,470 --> 00:49:45,080
Süper hızlı erişim olsun, böylece
Nerede sizin değer karma karar.

1062
00:49:45,080 --> 00:49:48,059
Çok kartlar örnek gibi,
Ben süper hızlı kararlar.

1063
00:49:48,059 --> 00:49:49,600
Kalpler elmas buraya, buraya.

1064
00:49:49,600 --> 00:49:52,180
Aynı burada, A buraya,
D B buraya, buraya.

1065
00:49:52,180 --> 00:49:55,740
Yani süper hızlı look-up ve eğer
Eğer bir durumda rastlıyorum

1066
00:49:55,740 --> 00:49:59,429
Eğer var çarpışmalar, iki
Aynı isimde insanlar, iyi o zaman

1067
00:49:59,429 --> 00:50:00,970
Sadece bunları birbirine bağlayan başlar.

1068
00:50:00,970 --> 00:50:03,900
Ve belki onları kriteri tutmak
alfabetik, belki yok.

1069
00:50:03,900 --> 00:50:05,900
Ama en azından şimdi dinamizm var.

1070
00:50:05,900 --> 00:50:10,250
Yani bir taraftan biz süper hızlı olması
sabit zaman ve lineer zamanın tür

1071
00:50:10,250 --> 00:50:14,110
Bu bağlantılı listeler halinde yer
biraz uzun olsun başlar.

1072
00:50:14,110 --> 00:50:16,880
>> Yani bir aptal bu tür
Önce geeky şaka yıl.

1073
00:50:16,880 --> 00:50:19,590
CS50 kesmek-a-thon anda,
Öğrenciler iade ettiğinizde,

1074
00:50:19,590 --> 00:50:22,040
Bazı TF veya CA, her yıl
düşünüyor o kadar koymak komik

1075
00:50:22,040 --> 00:50:27,772
Böyle bir işaret, nerede o sadece
Adın bir A ile başlıyorsa eğer gelir,

1076
00:50:27,772 --> 00:50:28,870
Bu şekilde gitmek.

1077
00:50:28,870 --> 00:50:31,110
Adın başlarsa
Bir B, bu-- Tamam gidin,

1078
00:50:31,110 --> 00:50:33,290
belki daha sonra yarıyılda komik.

1079
00:50:33,290 --> 00:50:36,420
Ama başka bir var
da bunu yapmanın yolu.

1080
00:50:36,420 --> 00:50:37,410
Geri o gel.

1081
00:50:37,410 --> 00:50:38,600
>> Yani bu yapı var.

1082
00:50:38,600 --> 00:50:40,420
Ve bu bizim son bir
Bugün için yapı,

1083
00:50:40,420 --> 00:50:42,400
hangi bir tray denilen şeydir.

1084
00:50:42,400 --> 00:50:47,140
Herhangi bir nedenle kısa bir T-R-I-E,
alımı için, ancak tray denir.

1085
00:50:47,140 --> 00:50:51,389
Bu nedenle bir tray bir ilginç
Bu fikirlerin bir sürü amalgam.

1086
00:50:51,389 --> 00:50:52,930
Biz daha önce gördüğümüz bir ağaç, var.

1087
00:50:52,930 --> 00:50:54,180
Bu ikili arama ağacı değil.

1088
00:50:54,180 --> 00:50:58,410
Bu, çocukların herhangi bir sayı ile bir ağaç var
ancak tray çocuk her

1089
00:50:58,410 --> 00:51:00,090
bir dizidir.

1090
00:51:00,090 --> 00:51:04,790
Boyut dizisi, 26 ya da belki 27 say
Eğer hyphenated isimleri desteklemek istiyorsanız

1091
00:51:04,790 --> 00:51:06,790
veya insanların isimleri kesme.

1092
00:51:06,790 --> 00:51:08,280
>> Ve bu nedenle bu, bir veri yapısıdır.

1093
00:51:08,280 --> 00:51:10,290
Ve yukarıdan bakarsanız
alt, gibi eğer

1094
00:51:10,290 --> 00:51:13,710
, orada üst düğüm, M bakmak
Orada soldaki şey işaret ederek,

1095
00:51:13,710 --> 00:51:17,665
bu daha sonra, A, X, W, E, L, L Bu edilir
Sadece bir veri yapısı olduğunu keyfi

1096
00:51:17,665 --> 00:51:19,120
insanların isimlerini saklamak olduğunu.

1097
00:51:19,120 --> 00:51:25,720
Ve Maxwell sadece takip ederek depolanır
diziye diziye dizinin bir yol.

1098
00:51:25,720 --> 00:51:30,050
Bir tray ilgili ama şaşırtıcı ne
Bu bir bağlantılı liste ise ve hatta

1099
00:51:30,050 --> 00:51:34,520
Bir dizi, biz şimdiye kadar kazanılmış en iyisidir
lineer zaman ya da logaritmik zaman seyir

1100
00:51:34,520 --> 00:51:35,600
Birisi yukarı.

1101
00:51:35,600 --> 00:51:40,530
Bir tray Bu veri yapısı, eğer içinde
Benim veri yapısı içinde bir isim var

1102
00:51:40,530 --> 00:51:43,720
ve ben Maxwell arıyorum, ben
oldukça hızlı onu bulmak için gidiyor.

1103
00:51:43,720 --> 00:51:47,910
Ben sadece M-A-X-W-E-L-L arayın. Eğer
Bu veri yapısı, aksine,

1104
00:51:47,910 --> 00:51:51,830
Bir varsa N, bir milyon ise
Bu veri yapısı milyon isimleri

1105
00:51:51,830 --> 00:51:57,100
Maxwell hala olacak
keşfedilebilir sadece M-A-X-W-E-L-L sonrası

1106
00:51:57,100 --> 00:51:58,090
adımlar.

1107
00:51:58,090 --> 00:52:01,276
Ve David-- D-A-V-I-D adımları.

1108
00:52:01,276 --> 00:52:03,400
Diğer bir deyişle, bina
olan bir veri yapısı

1109
00:52:03,400 --> 00:52:07,240
var olan bu dizilerin hepsi, her biri
kendileri, rastgele erişim desteği

1110
00:52:07,240 --> 00:52:11,090
İnsanların 's bakarak başlayabilirsiniz
bu süre bir miktar kullanarak isim

1111
00:52:11,090 --> 00:52:14,340
değil sayısı ile orantılı
veri yapısı şeyler,

1112
00:52:14,340 --> 00:52:16,330
gibi bir milyon varolan isimler.

1113
00:52:16,330 --> 00:52:20,135
Bulmak beni alır süre
M-A-X-B-E-L-L Bu veri yapısı içinde

1114
00:52:20,135 --> 00:52:22,260
orantılı değil
veri yapısının boyutu,

1115
00:52:22,260 --> 00:52:25,930
ama adının uzunluğuna.

1116
00:52:25,930 --> 00:52:28,440
Ve gerçekçi
isimler biz arıyoruz

1117
00:52:28,440 --> 00:52:29,970
Asla uzun deli olacak.

1118
00:52:29,970 --> 00:52:32,600
Belki birisi 10 karakteri vardır
20 karakter ismi.

1119
00:52:32,600 --> 00:52:33,900
Bu doğru, kesinlikle sonlu değil mi?

1120
00:52:33,900 --> 00:52:37,110
Yeryüzünde insan vardır kim
mümkün olan en uzun ada sahip,

1121
00:52:37,110 --> 00:52:39,920
ama bu isim bir sabittir
değer uzunluğu, değil mi?

1122
00:52:39,920 --> 00:52:41,980
Bu, herhangi bir anlamda farklılık yoktur.

1123
00:52:41,980 --> 00:52:45,090
Bu yüzden, bu şekilde, biz ettik
Bir veri yapısı elde

1124
00:52:45,090 --> 00:52:47,800
O zaman sabiti look-up olduğunu.

1125
00:52:47,800 --> 00:52:50,670
Bu bir dizi adım sürer
giriş uzunluğuna bağlı olarak,

1126
00:52:50,670 --> 00:52:54,250
isim değil numara
veri yapısı içinde.

1127
00:52:54,250 --> 00:52:58,700
Biz isimlerin sayısını iki katına Yani eğer
Bir milyar iki milyar ila gelecek yıl,

1128
00:52:58,700 --> 00:53:03,720
bulgu Maxwell sürecekse
Yedi adım aynı sayıda

1129
00:53:03,720 --> 00:53:04,650
Onu bulmak için.

1130
00:53:04,650 --> 00:53:08,810
Ve böylece biz elde ettik görünüyor
çalışma süresi bizim kutsal kasesi.

1131
00:53:08,810 --> 00:53:10,860
>> Yani hızlı duyurular bir çift.

1132
00:53:10,860 --> 00:53:11,850
Sınav sıfır geliyor.

1133
00:53:11,850 --> 00:53:14,600
Dersin web sitesinde bu konuda daha fazla
önümüzdeki birkaç gün boyunca.

1134
00:53:14,600 --> 00:53:17,120
Pazartesi günü bir bayram var lecture--
Burada Harvard'da Pazartesi günü.

1135
00:53:17,120 --> 00:53:18,850
Bu, New Haven değil
bu yüzden sınıf alıyoruz

1136
00:53:18,850 --> 00:53:20,310
Pazartesi günü ders için New Haven.

1137
00:53:20,310 --> 00:53:22,550
Herşey çekilecek
ve her zamanki gibi canlı akış

1138
00:53:22,550 --> 00:53:24,900
ama en sonunda bugün edelim
30 saniyelik bir klip ile

1139
00:53:24,900 --> 00:53:26,910
sözde "Derin Düşünceler"
Daven Farnham tarafından hangi

1140
00:53:26,910 --> 00:53:30,850
Cumartesi geçen yıl esinlenilmiştir
Gece Live'ın "Derin Düşünceler"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy tarafından hangi
Şimdi mantıklı olmalıdır.

1142
00:53:35,700 --> 00:53:38,810
>> FİLM: Ve şimdi, "Derin
Daven Farnham tarafından Düşünceler ".

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tablo.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> KONUŞMACI 1: Pekala, o an için bu.

1147
00:53:47,660 --> 00:53:48,805
Gelecek hafta görüşürüz.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: eylem görmek için.

1150
00:53:56,680 --> 00:53:58,304
Yani şimdi o bir göz atalım.

1151
00:53:58,304 --> 00:53:59,890
Yani burada biz bir sıralanmamış dizi var.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, önde ve yeniden gidebilir
Sadece bir saniye için bu, lütfen.

1153
00:54:04,860 --> 00:54:08,562
Pekâlâ, kameralar, yani haddeleme
eylem Doug, hazır olduğunda, tamam mı?

1154
00:54:08,562 --> 00:54:11,020
Doug: Pekala, ne
Burada var bir sıralanmamış dizidir.

1155
00:54:11,020 --> 00:54:13,960
Ve ben bütün elemanları renkli ettik
aslında olduğunu göstermek için kırmızı,

1156
00:54:13,960 --> 00:54:14,460
unsorted.

1157
00:54:14,460 --> 00:54:17,960
Yani ilk şey yaptığımız hatırlamak
biz dizi sol yarısını sıralamak olduğunu.

1158
00:54:17,960 --> 00:54:20,630
Sonra sağa sıralamak
Dizinin yarısı.

1159
00:54:20,630 --> 00:54:22,830
Ve ya-da, ya-da, ya-da,
Beraber onları birleştirmek.

1160
00:54:22,830 --> 00:54:24,520
Ve biz tamamen sıralı dizi var.

1161
00:54:24,520 --> 00:54:25,360
Yani işler birleştirmeli sıralama nasıl.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: dur, dur, dur,
kes, kes, kes, kes.

1163
00:54:27,109 --> 00:54:30,130
Doug, sadece ya-da olamaz, ya-da,
ya-da, birleştirme sıralama yolumuzu.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: ben yaptım.

1165
00:54:31,970 --> 00:54:32,832
Bu iyi.

1166
00:54:32,832 --> 00:54:33,540
Biz gitmek için iyi bir konum.

1167
00:54:33,540 --> 00:54:34,760
Sadece haddeleme tutalım.

1168
00:54:34,760 --> 00:54:35,380
Her neyse,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Sen açıklamak zorunda
daha tam olarak bundan daha.

1170
00:54:37,800 --> 00:54:39,999
Bu sadece yeterli değil.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, biz değiliz
birine geri gitmek gerekir.

1172
00:54:41,790 --> 00:54:42,350
Bu iyi.

1173
00:54:42,350 --> 00:54:45,690
Neyse, biz merge-- ile devam edersek
Ian biz filme ortasındayız.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Biliyorum.

1175
00:54:46,612 --> 00:54:49,320
Ve biz sadece ya-da olamaz, ya-da,
tüm süreç boyunca ya-da.

1176
00:54:49,320 --> 00:54:52,200
Sen nasıl açıklamak zorunda
İki taraf birbirine birleştirilir.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Ama biz zaten ettik
açıkladı nasıl iki sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Sadece gösterilen ettik
Onları bir birleştirme dizisi.

1179
00:54:55,321 --> 00:54:56,486
Doug: Onlar süreci biliyorum.

1180
00:54:56,486 --> 00:54:57,172
Onlar iyi.

1181
00:54:57,172 --> 00:54:58,380
Biz bunun üzerine on kez gittim.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Sadece sağ atlanır.

1183
00:55:00,330 --> 00:55:03,360
Biz bir geri gidiyoruz, sen
Bunun üzerine sen ya-da, ya-da yapamam.

1184
00:55:03,360 --> 00:55:05,480
Geri birine tamam.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: Ben geri gitmek zorunda
Slaytlar arasında durmadan?

1186
00:55:07,833 --> 00:55:08,332
Tanrım.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Bu altıncı kez, Ian gibi.

1189
00:55:13,004 --> 00:55:13,940
Bu iyi.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Pekala.

1191
00:55:15,200 --> 00:55:16,590
Hazır mısın?

1192
00:55:16,590 --> 00:55:17,400
Büyük.

1193
00:55:17,400 --> 00:55:18,950
Eylem.