>> KONUŞMACI 1: Pekala, bu CS50 Bu haftanın beş sonudur.
Ve bu son kez hatırlamak biz başladı meraklısı verilere bakarak
çözmek için başladı yapılar tanıtmak başladı sorunlar,
yeni sorunlar, ancak bu anahtarı parçacığı sıralama oldu biz
düğümden düğüme yapmaya başladı.
Yani tabii ki bu Bir tek başına bağlantılı liste.
Ve tarafından tek başına, bağlı Ben sadece bir tane var demek
Bu düğümlerin her biri arasında geçirin.
Eğer meraklısı yapabilirsiniz çıkıyor çift ​​bağlantılı listeler gibi şeyler
Eğer bir ok var sayede , her iki yönde gidiş hangi
Belirli verimliliği ile yardımcı olabilir.
Ama bu sorunu çözmüş?
Nedir bu sorun çözmek mi?
Pazartesi günü neden umurunda ki?
Neden, teoride, biz Pazartesi günü umurumda mı?
O ne yapar?
>> HEDEF KİTLE: Biz dinamik olarak yeniden boyutlandırmak olabilir.
>> KONUŞMACI 1: Tamam, biz bu yüzden dinamik olarak yeniden boyutlandırmak.
Peki ikiniz de yapılır.
Yani dinamik bu yeniden boyutlandırabilirsiniz Veri yapısı, bir dizi ise,
hatırlama, bir bilmek zorunda priori ne kadar boşluk istediğiniz
ve biraz daha ihtiyacınız varsa uzay, şans dışında tür konum.
Sen yepyeni bir dizi oluşturmak zorunda.
Siz tüm taşımak zorunda sizin birinden diğerine veri
Sonunda eski dizi ücretsiz yapabilirsiniz ve daha sonra devam edersek.
Hangi sadece çok pahalı hissediyor ve çok verimsiz ve gerçekten bu olabilir.
Ama bu iyi değil.
Biz bir bedel ödemek, tek neydi daha belirgin fiyatlar biz
Bağlantılı bir listesini kullanarak ödeme?
>> HEDEF KİTLE: Biz kullanmak zorunda her biri için çift boşluk.
KONUŞMACI 1: Evet, bu yüzden ihtiyacımız en az iki katı kadar bir alan olarak.
Aslında, ben fark bu resim en hatta biraz yanıltıcı,
Çünkü modern bir sürü CS50 IDE bilgisayarlar, bir işaretçi veya adres
Aslında dört bayt değil.
Bu çok sık bu var gün, sekiz bayt, burada
dibe demektir çoğu gerçekte orada dikdörtgenler
iki kat tür Ben boğuldum Ne kadar büyük,
hangi üç kez olarak kullanıyor demektir biz başka türlü olabilir kadar boşluk.
Şimdi, aynı zamanda, biz konum Hala bayt konuşuyor, değil mi?
Biz ille bahsetmiyoruz megabayt veya gigabayt
Bu verilere sürece yapıların büyük olsun.
>> Ve bu yüzden bugün düşünmeye başlar Verileri keşfetmek nasıl
daha verimli bir şekilde eğer Aslında veri büyür.
Ama meşrulaştırılmaz deneyelim İlk operasyon
Eğer bunlar üzerinde yapabileceğiniz Veri yapılarının türlü.
Bağlantılı gibi Yani bir şey Liste genellikle destekler
operasyonlar silmek istiyorum, takın ve arayın.
Ve ben bu ne demek istiyorsunuz?
Bu sadece, genellikle gelir insanlar bağlantılı liste kullanıyorsanız,
kendilerinin veya başkasının hayata geçirdi silme, ekleme gibi fonksiyonları,
ve arama yapabilirsiniz, böylece aslında bir şey yapmak
veri yapısı ile kullanım için yararlı.
Yani kısaca bir göz atalım biz uygulamak nasıl at
Bağlantılı bir liste için bazı kod aşağıdaki gibi.
>> Yani bu sadece bazı C kodu, hatta komple bir program
Gerçekten hızlı bir şekilde çırpılmış söyledi.
Bu dağıtımda çevrimiçi değil kod, aslında çalışmaz çünkü.
Ama sadece ettik fark Yorum dedi,
dot dot dot, bir şey var Orada, orada, bir şey nokta nokta nokta.
Ve Sadece bakalım sulu kısımlar nelerdir.
Yani üçüncü hatta, Bu şimdi hatırlamak
son bir düğüm ilan önerdi Zaman, bu dikdörtgen hedeflerden biridir.
Bu, biz N arayacağım bir int var ama biz bir şey diyebiliriz,
ve daha sonra bir yapı düğüm yıldızı yanındaki denir.
Ve sadece, ikinci açık olması çizgi, hat altı tarihinde, o da ne?
Bizim için ne yapıyor?
Kesinlikle daha görünüyor çünkü bizim her zamanki değişkenler daha şifreli.
>> HEDEF KİTLE: O biri üzerinde hareket yapar.
>> KONUŞMACI 1: It biri üzerinde hareket yapar.
Ve, daha kesin olarak o adresi saklayacak
olması gerekiyordu düğümün semantik yanında, değil mi?
Bu yüzden gitmiyor mutlaka bir şey taşıyın.
Sadece gidiyor olan bir değeri saklamak
adresi olacak Bazı diğer düğümün,
Biz yapı söylediğim bu yüzden ve işte düğüm yıldız, yıldız ifade eden
Bir işaretçi veya bir adres.
Tamam, şimdi biz olduğunu varsayalım eğer Elimizdeki mevcut bu N ve atalım
başkasının olduğunu varsayalım tamsayılar bir sürü takılı
bağlantılı liste halinde.
Ve bu bağlantılı liste Bir noktada tarafından işaret
olan bir değişken olarak adlandırılan liste Bir parametre olarak burada geçti,
nasıl hattı hakkında gitmek 14 arama uygulayan?
Diğer bir deyişle, uygulama am halinde Amacı hayatında işlev
Daha sonra bir int ve almaktır Bağlantılı bir listenin başında,
Bu bağlantılı listesine bir göstericidir.
İlk gibi, ben David kim düşünüyorum Gönüllü, Pazartesi günü oldu
o işaret edildi Bütün bağlantılı liste,
biz geçiyoruz sanki bulunuyor David burada argüman olarak.
Nasıl bu listeyi geçme gidiyorsun?
Peki, bu çıkıyor ki olsa bile işaretçileri, bize şimdi nispeten yeni
Biz nispeten yapabilirsiniz delikanlı.
>> Ben devam edeceğim ve geçici bir değişken beyan
Kongre tarafından sadece gidiyor için, PTR işaretçisi olarak adlandırılan, ya da
ama istediğiniz her şey diyebiliriz.
Ve ben başlatmak için gidiyorum listenin başına.
Yani bir tür bu düşünebilirsiniz Bana öğretmen olarak geçen gün,
tür birisine işaret gönüllü olarak bizim insanlar arasında.
Yani bu geçici bir değişken değilim sadece aynı şeye işaret
bizim tesadüfen adlı bu Gönüllü David de işaret ediyordu.
Şimdi ibre ise boş değil, çünkü hatırlama
O boş bazı özel gözcü değeri , listenin sonuna çizmektedir
Ben işaret değilim iken yani Bizim son gönüllü gibi zemin
oldu, en önde gidelim ve aşağıdakileri yapın.
Pointer-- Eğer şimdi ben tür istiyorum Biz öğrenciyle yaptıklarını yapmaya
structure-- işaretçi nokta ise bir sonraki equals-- işaretçi nokta N, eşit değil ise
Değişken N, eşittir geçirilen oldu argüman,
sonra ben devam etmek istiyorum ve gerçek dönmek demek.
Ben içinde sayısı N bulduk Benim bağlantılı liste düğümlerden biri.
Ama nokta artık Bu bağlamda çalışır
işaretçi, PTR, çünkü Gerçekten bir gösterici, bir adres,
biz aslında acayip can sözdizimi nihayet bir parça kullanın
marka bu tür Sezgisel hissi ve aslında
gitmek anlamına gelir burada bir ok kullanmak Orada tamsayı o adresi.
Bu yüzden de çok benzer Nokta operatörü ruhu,
ancak gösterici bir gösterici değil çünkü ve gerçek bir yapı kendisi
biz sadece oku kullanın.
>> Yani eğer geçerli düğüm ben, Geçici değişken, işaret ediyorum
N, ne yapmak istiyorsun değil mi?
Eh, benim insan gönüllüler ile Geçen gün burada vardı,
İlk insan bir ben değilse istiyorum ve belki de ikinci insan değil
İstediğim tek ve üçüncüsü, ben hareketli fiziksel tutmak gerekir.
Gibi nasıl bir liste üzerinden adım mı?
Biz bir dizi vardı, sen Sadece ben artı artı gibi yaptım.
Ancak bu durumda, bu yeterlidir Bir sonraki, işaretçi, alır, işaretçi yapmak.
Diğer bir deyişle, bir sonraki alan sol elin bütün gibi
Pazartesi günü insan gönüllüler Bazı başka bir düğüme işaret kullanarak idi.
Bunlar sonraki komşuları vardı.
>> Bu listede gezinmek için istiyorsanız, Ben sadece, artık ben yapmak artı artı yapamam
Bunun yerine söylemek zorunda Ben, işaretçi, gidiyor
Bir sonraki alan ne olursa olsun eşit, Bir sonraki alan, sonraki alandır olduğunu
Bu sol ellerin aşağıdaki Biz sahne işaret vardı o
Bazı sonradan değerlere.
Ve ben üzerinden olsun bütün o yineleme,
ve nihayet, ben olmaması boş vurdu Bulunan N yine, ben sadece return false.
Yani yine, biz burada yapıyoruz hepsi, Bir an önce resmi olarak başına,
işaret ederek başlıyor muhtemelen listenin başında.
Ve sonra ben kontrol değeri Ben dokuz eşit arıyorum?
Eğer öyleyse, ben gerçek dönmek ve ben bittim.
Değilse, Elimi güncelleyin AKA gösterici, işaret
Bir sonraki okunun yerde ve Daha sonra yanındaki ok konumu,
ve bir sonraki.
Ben sadece bu dizi üzerinden yürüyorum.
>> Yani yine, kimin umurunda?
Gibi bunun için bir madde nedir?
Peki, biz tanıttı hatırlatmak bir yığın kavramı, hangi
o olduğu gibi soyut bir veri sürece türüdür bir C şey, bir CS50 şey değil,
bu soyut bir fikirdir, bu fikir üst üste şeyler istifleme
Bu uygulanabilir farklı şekillerde salkımları.
Ve biz teklif tek yönlü oldu Bir dizi ya da bir bağlantılı liste ile.
Ve bir o canonically çıkıyor Yığın en az iki operasyonları destekler.
Ve buzz kelimeler için, itme yığına şey itmek,
Yeni bir tepsi gibi yemekhane, veya pop,
hangi üstteki kaldırmak demektir yemek yığını arasından tepsi
salonu, ve daha sonra belki bazı diğer işlemler de.
Peki nasıl yapısını tanımlamak olabilir Şimdi bir yığın diyorsun değil mi?
>> Peki, biz gereği tüm var diyorum C. bizim emrinde sözdizimi,
Bana bir tür tanımı vermek Bir yığının içinde bir yapı,
Ben bölgesinin bir dizi olduğunu söylemek için gidiyorum Bütün sayıların demet ve ardından boyutu.
Yani diğer bir deyişle, ben istiyorum kodu uygulamak için,
Gitmeme ve sadece tür izin Bu ne söylediğini çizin.
Bu söylediğini Yani, bana ver bir dizi var yapısı,
ve ben, kapasite ne olduğunu bilmiyorum ben ettik o görünüşte bazı sabit var
başka yerde tanımlanmış ve bu iyi.
Ancak, sadece bir varsayalım iki, üç, dört, beş.
Yani kapasitesi 5 olduğunu.
Içinde bu eleman benim yapı numaralarını çağrılır.
Ve sonra bir ihtiyaç diğer değişken görünüşte
Başlangıçta ben gidiyorum denilen boyut sıfıra başlatıldı şart.
Hiçbir şey de varsa yığın, boyut, sıfır
ve sayıları çöp değerleri var.
Ben henüz içeride ne hiçbir fikrim yok.
>> Ben itmek istiyorsanız Yani yığına şey,
Ben işlev itme çağrı varsayalım, ve Ben, sayı 50 gibi, 50 itmek demek
nereye önereceğini Ben bu dizide çizmek?
Beş farklı olası cevaplar var.
Nereye numara 50 itmek istiyor musunuz?
Burada amaç, tekrar, çağrı Fonksiyon itme, bir argüman iletirsiniz
50, bunu nereye koyacağım?
Beş possible--% 20 şans bir doğru tahmin.
Evet?
>> HEDEF KİTLE: Uzak doğru.
>> KONUŞMACI 1: Uzak doğru.
% 25 şans var bir doğru tahmin.
Yani aslında iyi olurdu.
Geleneksel olarak, bir dizi ile söylerim, Biz genellikle, solda başlamak istiyorum
ama biz kesinlikle olabilir Sağdaki başlar.
Yani burada spoiler ben olurdu Muhtemelen solda çizmek için gidiyoruz,
Sadece normal bir dizide nerede gibi Ben sağa sola gidiyor başlar.
Ama çevirebilirsiniz eğer aritmetik, ince.
Bu sadece geleneksel değil.
Tamam, ben bir yapmak gerekiyor ama daha değişiklik.
Şimdi ben bir şey itti ettik yığına, sırada ne var?
>> Pekala, boyutu artırmak gerekiyor.
Bu yüzden bana öncesinde ve sadece gidelim Sıfır olan bu güncelleme.
Ve onun yerine şimdi, ben gidiyorum değerinde tek koymak.
Ve şimdi başka bir itme varsayalım yığına sayısı 51 gibi.
Eh, ben bir daha yapmak zorunda boyutuna iki kadardır değişim.
Ve sonra bir tane daha itmek varsayalım 61 gibi yığına sayısı
Şimdi boyutunu güncellemeniz gerekir bir daha Zaman ve boyut olarak değer 3 olsun.
Ve şimdi pop diyoruz herhalde.
Şimdi kongre tarafından, pop, bir argüman almaz.
Bir yığın ile, tüm Tepsi metafor noktası
Eğer takdir yetkisine sahip kalmamasıdır O tepsiyi gidip, tüm yapabileceğiniz
dan üstteki birini pop olduğunu Yığın, sırf.
İşte bu veri yapısı böyle yapar.
>> Eğer mantık tarafından Yani pop ne kapalı geliyor demek?
Yani 61.
Yani gerçekten bilgisayar nedir bellekte yapacaksın?
Ne benim kod ilgisi var?
Ne önereceğini Biz ekranda değişiklik?
Ne değiştirmek gerekir?
Maalesef?
Yani biz 61 kurtul.
Yani kesinlikle yapabilirim.
Ve ben 61 kurtulabilirsiniz.
Ve sonra ne diğer değişim gerçekleşmesi gerekiyor?
Boyutu büyük olasılıkla iki geri gitmek zorunda.
Ve böylece iyi.
Ama bir dakika, büyüklüğü bekleyin bir an önce üç oldu.
Sadece hızlı bir sağlamlık denetimi yapalım.
Nasıl biz biliyor muydunuz 61 kurtulmak istedim?
Biz haşhaş Çünkü.
Ve bu yüzden bu ikinci özellik boyutu var.
>> Ben, bir dakika bekle Haftanın iki geri düşünme
bahsediyoruz başladığımda Bu konum sıfır diziler,
Bu konum biriydi bu yeri oldu İki, bu konum, üç, dört olduğunu
Göründüğü gibi büyüklüğü arasındaki ilişki
ve istediğim eleman çıkarmak diziden sadece ne gibi görünüyor?
Boyut eksi bir.
Ve böylece nasıl insan olarak var Biz 61 önce gelir biliyorum.
Nasıl bilgisayar bilmek oluyor?
Ne zaman kod nerede muhtemelen boyutu eksi birini yapmak istiyorum,
böylece üç eksi bir, iki, ve olduğunu Biz 61 kurtulmak istediğiniz anlamına gelir.
Ve sonra biz gerçekten güncelleyebilirsiniz o boyutta böylece boyutu artık
Sadece iki üç gider.
Ve sadece bilgiçlik olmak gerekirse, ben gidiyorum Birazdan, işim olduğunu önerecek?
Sezgisel önerdi Doğru ben 61 kurtulmalıdır.
Ama yok ben tür çeşit 61 kurtulmuş?
Ben etkin bir şekilde unuttum o aslında var.
Eğer okudum ve eğer geri PSET4 düşünüyorum adli tıp ile ilgili makale, PDF
Biz bu çocuklar okumak, ya da PSET4 için bu hafta okuyacaktır.
Bu aslında germane olduğunu hatırlayın bilgisayar adli tıp bütün fikir.
Ne bir bilgisayar genellikle yok olduğunu bir şey olduğu, sadece, unutur
ama gitmek ve benzeri yok dışarı veya geçersiz kılma kazımak deneyin
birler ve sıfırlar olan bitler ya da başka bir rasgele bir desen
Sürece kendinizi bu kadar kasıtlı yok.
Yani sezgi oldu Tamam, 61 kurtulalım.
Ama gerçekte, biz uğraşmak zorunda değilsiniz.
Biz sadece unutmak gerekir Bizim boyutunu değiştirerek var.
>> Şimdi bu yığının bir sorun var.
Bazı şeyleri zorlamaya devam ederse yığına, ne
Açıkçası ne olacak Sadece birkaç dakika süre içinde?
Biz alanı tükenmeye gidiyoruz.
Ve biz ne yapacağız?
Biz tür mahvoluruz.
Bu uygulama izin vermez kullanma çünkü bize, dizi yeniden boyutlandırmak
Bu sözdizimi, eğer Haftanın iki geri düşünmek,
Eğer beyan ettik bir kere Bir dizinin büyüklüğü,
Henüz nerede bir mekanizma görmedim Eğer dizinin boyutunu değiştirebilirsiniz.
Ve gerçekten C bu özelliği yoktur.
Derseniz, bana beş ver Nths, onları aramak sayılar,
Bu onu almak için gidiyoruz hepsi bu.
Bu yüzden Pazartesi gününden itibaren şimdi var Bir çözüm ifade yeteneği
olsa da, biz sadece oynamak için gereken Bizim yığının tanımı
Bazı sabit kodlanmış dizi olmamak, ama sadece bir adres saklamak için.
>> Şimdi neden bu?
Şimdi biz sadece rahat olmak zorunda Aslında benim program çalıştığında o,
Ben muhtemelen gidiyorum insan sormak zorunda,
kaç sayı saklamak istiyorsun?
Yani giriş yere gelmek zorunda.
Ama bunu öğrendikten sonra numara, o zaman ben sadece can
vermek işlevi ne kullanmalıyım Bana bellek yığın?
Ben malloc kullanabilirsiniz.
Ve ben herhangi bir sayıda söyleyebiliriz bayt geri bu Nths için istiyorum.
Ve tüm sayıları saklamak zorunda Bu yapının içinde burada değişken
Ne olmalı?
Gerçekte gider Bu senaryoda numaralar?
Evet, ilk bir işaretçi bu bellek öbek bayt
veya daha özel olarak, adres Bu bayt ilk.
Bu bir ise farketmez bayt veya milyar bayt,
Ben sadece ilk umurumda gerekir.
Çünkü neyi malloc garantiler ve İşletim sistemi garanti,
olduğu hafıza I yığın olsun, bitişik olacak.
Boşluklar orada olacak değil.
Ben 50 için sordum eğer öyleyse bayt veya 1000 bayt
hepsi olacağız arka arkaya arkaya.
Ve çok uzun ben, nasıl ne kadar büyük hatırlıyorum çok ben bilmem gereken, tüm istedi
bu tür ilk adresidir.
>> Yani şimdi biz kod yeteneği var.
Gerçi, o bizi almaya gidiyor daha fazla zaman, bu kadar yazmak için
şimdiye kadar bu bellek tahsis olabilir Sadece orada farklı bir adres depolamak
biz bile bir büyük veya isterseniz belleğin küçük bir yığın.
Yani burada bir ticaret kapalı olarak.
Şimdi dinamizm olsun.
Biz hala var contiguousness Ben iddia ediyorum.
Malloc bize verecektir çünkü bellek bitişik bir yığın.
Ama bu bir ağrı olacak Bizim için boyun, programcı,
Aslında kadar kod.
Bu sadece daha fazla iş var.
Biz ne benzer kodu gerekir Sadece bir an önce dışarı vurarak.
Çok yapılabilir, ancak bu karmaşıklık ekler.
Ve böylece geliştirici zamanı, programcı Zaman başka kaynak
Biz harcamak gerekir diye biraz zaman yeni özellikler elde etmek.
Ve sonra tabii ki bir kuyruk var.
Biz bu girmeyeceğim çok detaylı bir.
Ama ruhu çok benzer.
Ben bir kuyruk uygulamak ve olabilir bunun karşılık gelen işlemleri,
enqueue veya dequeue eklemek veya kaldırmak gibi, o, bunu demenin bir yolu meraklısı
enqueue ya dequeue, aşağıdaki gibi.
Ben sadece kendime bir yapı verebilir yine bir sayının dizi var,
yine bir boyuta sahiptir, ama neden şimdi ihtiyacım var
Bir sıranın önünde takip etmek?
Bilmem gerek yoktu Benim yığının ön.
Peki, eğer tekrar bir queue-- sadece sabit atalım
beş gibi sahip olarak kod Burada potansiyel olarak tamsayılar.
Yani bu, sıfır, bir, iki, üç, dört.
Bu olacak tekrar aradı numaralar.
Ve bu boyutta çağrılır.
>> Neden yeterli değil Sadece boyutu var mı?
Peki, üzerinde bu aynı numaraları basalım.
Ben de kuyruğa veya itti pushed--.
Şimdi o 50 enqueue ve edeceğiz 51 ve daha sonra 61 ve nokta nokta nokta.
Yani enqueue var.
Daha sonra 61, sonra 50, 51 kuyruğa.
Ve bu aynı görünüyor Bugüne kadar bir yığın,
dışında ben tek değişiklik yapmak gerekiyor.
Bu boyut güncellemeniz gerekir, bu yüzden gitmek Şimdi üç, bir ila iki sıfırdan.
Nasıl sıradan çıkarma mı?
Ne Dequeue ile olur?
Kim ilk önce bu liste dışı gelmelidir Apple Store çizgi olur?
Yani 50.
Dolayısıyla bu tür yanıltıcıdır bu zamanı.
Son kez Oysa o süper oldu kolay, sadece, boyutu eksi birini yapmak
Ben etkili benim dizinin sonuna olsun sayılardır, bu 61 kaldırır.
Ama 61 kaldırmak istemiyorum.
Ben, 50 almak isteyen 05:00 am oldu
için sıraya Yeni iPhone veya etajer.
Ve bu yüzden, 50 kurtulmak için sadece sağ, bunu yapamaz?
Ben 50 üzerinden geçebilir.
Ama biz sadece biz dedi çok anal olmak zorunda değilsiniz
olarak çizebilir veya veri gizlemek için.
Nerede olduğunu Biz sadece unutabilirsiniz.
>> Ama şimdi benim boyutunu değiştirmek durumunda İki, bu yeterli bilgi
Benim kuyruğunda olup bitenleri bilmek ister misiniz?
Pek sayılmaz.
Benim büyüklüğü, iki gibi ama Sıra nerede kaçta başlayacak,
Özellikle ben hala varsa Bellekte bu aynı numaralar.
50, 51, 61.
Yani hatırlamamız gerekiyor Şimdi ön nerede.
Ve bu yüzden ben önerdiği gibi Orada, biz sadece çağrıda edeceğiz
Olan ilk N. ön, değeri nedir olmalıydı?
Sıfır, listenin sadece başlangıç.
Ama şimdi sıra azaltma için boyut, biz sadece ön artırmak.
Şimdi, burada başka bir sorun var.
Yani devam edin zamanlar.
Bu sayısıdır varsayalım gibi 121, 124, ve daha sonra, kahretsin
Ben boş alan var.
Ama ben değilim, bir dakika bekleyin.
Hikayenin bu noktasında Yani, boyut, bir, iki olduğunu varsayalım,
üç, dört, böylece varsayalım boyutu, açık biri, dört olduğu
yani 51 ön olduğunu.
Burada başka bir numara koymak istiyorum, ancak, kahretsin, ben boş alan var.
Ama doğru, gerçekten değilim?
Ben biraz nereye koymak olabilir 171 gibi ek değer?
Evet, I could sadece tür Doğru, geri oraya gitmek?
Ve sonra 50 üzerinden çapraz veya Sadece 171 ile üzerine.
Ve neden merak ediyorsanız Bizim sayılar, yani rastgele var
Bu sık bilgisayar alınır CS50 sonra Harvard'da bilim dersleri.
Ama bu iyi bir optimizasyon oldu, şimdi çünkü uzay israf değilim.
Hala hatırlamak zorunda ne kadar büyük bu şey toplamıdır.
Beş toplam bulunuyor.
Çünkü ben .... istemiyorum 51 üzerine başlayın.
Yani şimdi ben hala alanı dışında duyuyorum, böylece aynı sorun daha önce olduğu gibi.
Ama nasıl şimdi görebiliyorum kodunuzda, muhtemelen
biraz daha yazmak zorunda karmaşıklığı gerçekleşmesi için.
Ve aslında ne operatörü C muhtemelen sağlar
Eğer sihirli Bu daireselliği mı?
Evet Modulo operatörü, yüzde işareti.
Yani bir sıraya hakkında tür serin ne Biz çizim diziler tutmak bile
Bu gibi düz çizgiler olarak, eğer tür kıvrılması olarak bu konuda düşünmek
etrafında bir çember olarak, sonra sadece sezgisel bu tür zihinsel işleri
Ben daha temiz biraz düşünmek.
Hala uygulamak zorunda kalacak kodunda bu zihinsel modeli.
Bu yüzden değil o kadar da zor, sonuçta, uygulama
ama biz yine de oldukça, size-- kaybetmek Bunu yapmazsak yeteneği yeniden boyutlandırmak için.
>> Biz dizinin kurtulmak için, biz Tek bir işaretçi ile değiştirin,
ve sonra bir yerde benim kod ben var Bir aslında hangi fonksiyonu oluşturacağına çağrı
Dizi denilen numaralar?
Malloc, veya benzeri bir işlevi, tam.
Yığınlar veya sıralarda Herhangi bir sorunuz.
Evet?
İyi soru.
Ne Modulo burada kullanabilirsiniz.
Yani genel olarak, kullanırken mod, bunu yapacağını
büyüklüğüne Bütün veri yapısı.
Yani bir şey beş veya kapasite, eğer gibi o sürekli var, muhtemelen yer almaktadır.
Ama modulo beş yapıyor Muhtemelen, yeterli değildir
Bilmemiz gereken, çünkü biz do burada ya burada ya da burada etrafında sarın.
Yani belki de sensin dahil etmek istediğiniz gidiyoruz
şey boyutu veya yanı sıra ön değişken.
Yani sadece bu nispeten var basit aritmetik ifade,
ama modulo anahtar bileşen olacaktır.
>> Yani kısa film eğer sen.
Bir animasyon bazı Başka bir üniversitede millet
biz ettik o araya Bu tartışma için uyarladı.
Jack öğrenme içerir kuyruklar ve istatistikleri hakkında gerçekler.
>> FİLM: Bir zamanlar, Jack adında bir adam vardı.
O arkadaşlar geldi, Jack bir püf noktası yoktu.
Yani Jack konuşmak için gitti En popüler adam biliyordu.
O Lou gitti ve ben ne yapmalıyım, diye sordu?
Lou onun arkadaşı olduğunu gördüm Gerçekten sıkıntılı oldu.
Peki, o sadece, başladı Eğer giymiş konum nasıl bakmak.
Eğer herhangi bir kıyafet yok mu Farklı bir görünüme sahip?
Evet, Jack dedi.
Eminim.
Evime gel ve Ben bunları size göstereyim.
Bu yüzden Jack'in gitti.
Ve Jack Lou kutusunu gösterdi Nerede o, bütün gömlek tuttu
ve pantolonunun ve onun çorap.
Lou görüyorum ki, dedi bir yığın tüm giysi.
Neden bazı giymiyorum kez süre diğerleri?
>> Jack, dedi de, ben , giysi ve çorap çıkarmak
Ben onları yıkamak ve koyun Onları uzak kutusunda.
Ardından bir sonraki geliyor Sabah ve yukarı ben hop.
Ben kutusuna gidin ve almak kapalı üst elbiselerimi.
Lou hızla gerçekleşen Jack sorun.
O, giysi, CD'ler tuttu ve yığın kitap.
O uzandı bir şey okumak veya giymek,
o üst kitap ya da iç çamaşırı seçerdim.
Sonra o bitince, o Hemen geri koymak istiyorum.
Geri o yığının en üstüne, giderdim.
Ben çözümü biliyorum, muzaffer Loud söyledi.
Sen öğrenmek gerekir bir sıra kullanmaya başlayabilirsiniz.
Lou Jack'in elbiselerini aldı ve dolaba astı.
Ve o boşaltılması ne zaman kutu, o sadece attı.
>> Sonra Jack sonunda şimdi, dedi gün, soldaki elbiselerini koymak
Onları uzak koyduğunuzda.
Sonra yarın sabah sizi elbiselerini almak, güneşi görmek için
satırın sonuna sağa, üzerinde.
Görmüyor musun? Lou dedi.
O kadar güzel olacak.
Bir kez şeyi giyeceğim önce iki kez bir şey giymek.
Ve sıralarında her şeyi ile Onun klozet ve raf,
Jack hissetmeye başladı kendinden oldukça emin.
Lou tüm sayesinde ve onun harika kuyruk.
KONUŞMACI 1: Tamam, sevimli.
Yani gerçekten Ne olup bittiğini Şimdi başlık altında üzerinde?
Biz işaretçiler olması, Biz Malloc sahip olduğu,
Biz oluşturma yeteneği var kendimiz için hafıza parçaları
dinamik.
Yani bu bir resim biziz geçen gün glimpsed.
Biz gerçekten durmadı Bunun üzerine, fakat bu resim
altında bulunmaktadır devam Şimdi haftadır kaput.
Ve böylece bu sadece temsil biz boğuldum bir dikdörtgen,
Bilgisayarınızın belleği.
Ve belki bilgisayarınız veya CS50 Kimlik, bellek ya da RAM gigabayt vardır
ya da iki gigabayt veya dört.
Bu gerçekten önemli değil.
İşletim sisteminiz Windows ya da Mac OS veya Linux,
esasen programı veriyor bu erişime sahip olduğunu düşünmek
bütünü için Bilgisayarınızın belleği
hatta çalışıyor olabilir ama Aynı anda birden çok program.
Yani gerçekte, bu gerçekten işe yaramazsa.
Ama bu bir yanılsama tür tüm programlarınızı verildi.
Yani eğer, bu RAM iki konser vardı Bilgisayar düşünmek nasıl olduğunu.
>> Şimdi tesadüfen, bunlardan biri şeyler bellek bu segmentlerden biri
Bir yığın denir.
Ve gerçekten her zaman bugüne kadar yazı kodu
Aradığınız bir örneğin main fonksiyon.
Herhangi bir zaman var olduğunu hatırlayın çizilmiş bilgisayarın bellek,
Ben her zaman bir çeşit çizmek Burada bir dikdörtgen yarısı
ve konuşurken rahatsız etmeyin Yukarıda ne hakkında.
Ana çağrıldığında, ben iddia Çünkü bellek bu şeridi olsun
Burada iner.
Ana Ve eğer bir fonksiyon denir swap gibi, iyi takas buraya.
Ve işte, çıkıyor nerede biten ediyor.
Bir yığın olarak adlandırılan şey Bilgisayarınızın belleği içinde.
Şimdi günün sonunda, Bu sadece adresleri olduğunu.
Bu, byte sıfır gibi Bayt biri, bayt 2 milyar.
Ama bu konuda düşünüyorsanız Bu dikdörtgen nesne olarak,
Tüm biz her yapıyoruz kez biz bir fonksiyonudur diyoruz
yeni bir bellek dilim katman.
Bir dilim bu işlevi veriyorsun Kendi bellek ile çalışmak.
>> Ve bu önemli olduğunu şimdi hatırlamıyorum.
Biz var çünkü eğer swap gibi bir şey
A ve B gibi iki yerel değişkenler Biz bir ve iki gelenler değerleri değiştirmek
İki ve biri hatırlama takas döndüğünde o,
Bu dilim sanki bulunuyor bellek sadece gitti.
Gerçekte, hala var Orada adli.
Ve bir şey aslında hâlâ orada.
Ama kavramsal, o kadar var gerçi tamamen gitti.
Ve böylece, ana iş herhangi bilmiyor Bu, bu takas fonksiyonu yapıldı
aslında o geçti sürece işaretçi veya başvuruya göre argümanları.
Şimdi, temel çözüm takas ile bu soruna
adrese göre bir şeyler geçiyor.
Ama çok, ne çıkıyor o kısmı yukarıda devam
dikdörtgenin tüm bu zaman Henüz daha fazla bellek orada var.
Ve ne zaman dinamik bellek ayrılamadı,
o getString, içinde olsun hangi Biz CS50 senin için yapıyorum
Kütüphane veya siz eğer malloc arayıp sormak
Bir yığın için işletim sistemi Bellek, bu yığından gelmez.
Başka bir yerden geliyor Bilgisayarınızın belleğinde
Bu yığın denir.
Ve herhangi bir farklı değil.
Aynı RAM bulunuyor.
Aynı bellek bulunuyor.
Bu kalmış sadece RAM bulunuyor Orada yerine buraya.
>> Ve böylece bu ne anlama geliyor?
Peki, bilgisayarınız varsa bellek sınırlı miktarda
ve yığın yüzden büyüyor konuşan ve yığın, uygun için
Bu ok, aşağı büyüyor.
Diğer bir deyişle, her bir zaman malloc diyoruz,
Eğer bir dilim verilen konum bellek, yukandan
Biraz sonra, alt sonra belki biraz alt, sen malloc çağrı her zaman,
Yığın, bu kullanım var, tür büyüyor,
Neye yakın ve daha yakın büyüyen?
Yığını.
Yani bu iyi bir fikir gibi görünüyor?
Gerçekten net değil nerede Yani, başka ne sen sadece yapabileceği
bellek sınırlı bir miktarda var.
Ama bu kesinlikle kötü.
Bu iki okları vardır birbirlerine kursu çökmesine.
>> Ve o kadar da kötü adamı, millet çıkıyor , programlama ile özellikle iyi
ve bilgisayar hacklemek için çalışıyor, Bu gerçeği yararlanabilir.
Aslında, en düşünelim Biraz pasajı.
Yani bu okuyabilirsiniz bir örnektir hakkında Wikipedia'da daha ayrıntılı.
Biz sizi işaret edeceğiz makale, eğer meraklı.
Ama bir saldırı genellikle var arabellek taşması olarak bilinen
İnsanlarda olduğunca uzun süre varlığını sürdüren işlemek için yeteneği vardı
Özellikle C. bilgisayarın bellek, Yani bu çok keyfi bir program,
ama en aşağıdan yukarıya onu okuyalım.
Argc karakter yıldızı argv içine ana.
Yani onu alır bir program komut satırı argümanları.
Ve tüm ana görünüşte çağrı yok Bir fonksiyon, basitlik için F diyoruz.
Ve ne geçer?
Birinin argv.
Yani F geçer ne olursa olsun Kelime kullanıcı yazdığınız olduğunu
sonra isteminde Programın ismi hiç.
O kadar Sezar veya Vigenere gibi hangi Eğer argv yapıyorsun çağırmak olabilir.
>> Peki F nedir?
F bir dize alır tamamen kendi argüman olarak,
AKA bir karakter yıldızı, aynı şey, bir dize olarak.
Ve bu keyfi denir Bu örnekte bar.
Ve sonra karakter c 12, Sadece meslekten olmayan şartlarını,
Bizim için yapıyor Char c dirseği 12 nedir?
Ne işe yarıyor?
Özellikle, bellek ayırma 12 karakter için 12 bayt.
Kesinlikle.
Ve sonra son satırı, karıştırın ve kopyalama, muhtemelen görmedim.
Bu bir dize kopya Amacı hayatında işlev
ikinci argüman kopyalamak için İlk argüman,
ama sadece kadar bayt belirli sayıda.
Yani üçüncü argüman diyor Kaç bayt kopyalamak gerekir?
Çubuğun uzunluğu, ne yazdığınız kullanıcı.
Ve içerikleri vardır, bu dizeyi bar
belleğe kopyalanan C'de işaret
>> Yani bu tür aptalca görünüyor ve öyle.
Bu yapmacık bir örnek, ama temsili var
saldırı vektörlerinin bir sınıfın, Bir program saldıran bir yol.
Tüm ince ve kullanıcı eğer iyi 11 karakter var bir kelime türleri
Daha az artı ters eğik çizgi sıfır veya.
Ne daha kullanıcı tipleri fazla ise 11 ya da 12 ya da 20 ya da 50 karakter?
Yapacak bu program nedir?
Potansiyel seg arıza. Gidiyor körü körüne kadar barda her şeyi kopyalamak için
olan uzunluğu için kelimenin tam anlamıyla barda her şey
adresine C Fakat C işaret Sadece preemptively 12 byte olarak vermiştir.
Ama hiçbir ek çek var.
Koşullar olursa yok.
Burada kontrol hiçbir hata yok.
>> Ve böylece bu program nedir yapacaksın sadece körü körüne bir
diğer bir şey kopyalayın.
Ve böylece bu çizerseniz bir resim olarak, burada
hafıza alanının sadece bir şerit.
Yani biz, altta fark Yerel değişken bar var.
Store-- gidiyor o yüzden işaretçi olduğunu, yerel argüman yerine
Dize çubuğunu saklamak için gidiyoruz.
Ve sonra sadece fark Yukarıda bir istif halinde,
Çünkü sormak her zaman yığını bellek,
o biraz gider resimsel üstünde,
Biz orada 12 bayt var haber.
Sol üst bir adet C dirseği sıfır ve bir Sağ alt bir adet C braket 11 olduğunu.
Bu sadece nasıl bilgisayarlar var Bunu ortaya koymak için gidiyor.
Yani sadece sezgisel, bar daha varsa olmak üzere toplam 12 karakter daha
olan ters bölü sıfır, 12 veya C dirseği 12 gidecek?
Ya da daha doğrusu nerede olduğunu 12. karakter veya karakter 13th,
gidiş yüzüncü karakter resimde sonuna kadar?
Üstünde veya altında?
>> Doğru, çünkü rağmen Yığın kendisi yukarı büyür
Eğer bir şeyler koyduk kez Bu, bu tasarım sebebiyle
üstten alta doğru bellek koyar.
Eğer fazla 12 bayt var eğer öyleyse, Eğer çubuğu üzerine başlamak için gidiyoruz.
Şimdi bu bir hata, ama var gerçekten büyük bir anlaşma.
Var çünkü Ama bu büyük bir anlaşma olduğunu bellekte oluyor daha fazla şeyler.
Yani burada nasıl olabilir var açık olması, merhaba koydu.
Ben isteminde Merhaba yazdıysanız.
'H-E-L-L-O eğik sıfır, içinde biter Bu 12 byte ve biz süper güvendeyiz.
Herşey iyi.
Ama bir şey yazarsanız Artık, potansiyel olarak var
bar uzaya sürünmeye gidiyor.
Ama daha kötüsü, bu döner Bütün bu zaman aşımı,
konuştuğumuz hiç olsa bile bu, yığın diğer şeyler için kullanılır.
Bu sadece yerel değişkenler değil.
>> C çok düşük seviyeli bir dildir.
Ve bu tür gizlice Ayrıca yığın kullanır
ne zaman hatırlamak işlevi ne denir
adres, önceki fonksiyonun olduğunu bu yüzden tekrar o işleve atlayabilirsiniz.
Yani ana çağrılar arasında, takas zaman şeyler yığını itti
sadece, yerel değişkenler swapları değil ya da argümanları, aynı zamanda gizlice itti
yığın üzerine temsil edilen Burada kırmızı dilim tarafından,
Ana adresi fiziksel olarak Bilgisayarınızın belleğinde,
böylece değiştirilebilir yapılır, bilgisayar Ben ana geri gitmek gerekir bilir
ve ana işlevi yürütme bitirmek.
Yani bu, şimdi tehlikeli çünkü eğer merhaba daha iyi daha fazla kullanıcı tipleri,
kullanıcının giriş clobbers şekilde ya da, kırmızı bölüme yazar
mantıklı eğer bilgisayarın sadece körü körüne kabul edeceğim
kırmızı dilim bayt olduğunu o dönmelidir hangi adresi
düşman ne ise yeterince akıllı ya da bayt dizisi koymak için şanslı
Orada bir adres gibi görünüyor, ancak kod adresi var
o bilgisayarı istediği yerine main yürütmek için?
>> Diğer bir deyişle, ne olursa Kullanıcı, komut istemine yazıyor
Sadece bir şey değil Merhaba zararsız gibi
ama eşdeğer kod aslında Bütün bu kullanıcının dosyaları silmek için?
Ya da bana kendi şifresini e-posta?
Ya da oturum başlatmak onların tuş vuruşlarını, değil mi?
Bir yolu var, en Bugün şart edelim Onlar merhaba sadece yazın ki
Dünya ya ad, onlar aslında olabilir
Kod, sıfır geçmek ve olanlar, bu bilgisayar
kod ve bir adres hem de hatalar.
Olsa Yani biraz soyut, eğer Yeterince düşmanca kod kullanıcı türleri
Burada olduğu gibi genelleme edeceğiz A. A krizi veya düşmanlar olduğunu.
Yani sadece kötü şeyler.
Biz umurumda değil sayılar ya da sıfır ya da olanları
Bugün, bu tür sonuna kadar bu kırmızı bölümü üzerine,
bayt bu sekansı edin.
O 835 C sıfır sekiz sıfır.
Ve şimdi burada Wikipedia'nın makale olarak Şimdi aslında başlarsanız, önerdi
Bilgisayarınız yıllarda bayt etiketleme Bellek, Wikipedia makalesi nedir
önerdi, bu ne adres ise O sol üst byte 80 C 0 3508 olduğunu.
>> Diğer bir deyişle, kötü biri ise, onun koduyla yeterince akıllı
Aslında burada bir numara koymak için o kod adresine tekabül
o enjekte bilgisayarın içine, sen
Bilgisayarı kandırmak olabilir bir şey yapıyor içine.
, Dosyalarını kaldırma e-posta şeyler, senin trafik koklama,
kelimenin tam anlamıyla bir şey olabilir bilgisayara enjekte.
Ve böylece bir bellek taşması özünde saldırı
sadece aptal, aptal Dizinin ağır basan o
onun sınırları kontrol yoktu.
Ve bu süper tehlikeli ne ve aynı zamanda süper güçlü
C biz gerçekten var olduğunu bellekte her yerde erişim.
Bu bize kalmış, programcılar, kim orijinal kod yazmak
Herhangi bir lanetlemek uzunluğunu kontrol etmek Biz manipüle ediyoruz diziler.
Yani açık olmak, düzeltme nedir?
Bu geri atarsanız Kod, yapmamalıyım sadece
çubuğun uzunluğunu değiştirmek ne Başka bir kontrol edilmelidir?
Başka ne için yapıyor olmalı Tamamen bu saldırıyı engellemek?
Ben sadece körü körüne söylemek istemiyorum gibi birçok bayt kopya gerektiğini
olarak çubuğun uzunluğudur.
Ben kopya söylemek istiyorum gibi birçok bayt bar olan
tahsis kadar Bellek ya da maksimum 12.
Yani durum eğer çeşit gerekir Bu çubuğun uzunluğunu kontrol yapar,
ama 12, biz sadece zor kod aşarsa Mümkün olan maksimum mesafe olarak 12.
Aksi takdirde sözde tampon taşma saldırısı olabilir.
Bu slaytlar alt kısmında, Daha fazla okumak için meraklı iseniz
Gerçek orijinal makale Eğer bir göz atın isterseniz.
>> Ama şimdi, fiyatların arasında yetersizlikler burada ödedi.
Yani bu bir hızlı oldu En düşük seviye göz nedir
sorunlar biz şimdi ortaya çıkabilir Bilgisayarın bellek erişimi vardır.
Ama başka bir sorun, biz Zaten Pazartesi günü tökezledi
sadece verimsizlik oldu Bağlantılı bir listenin.
Biz geri doğrusal zaman vardır.
Biz artık bitişik dizi var.
Biz rastgele erişim yok.
Biz köşeli ayraç notasyonu kullanamazsınız.
Biz kelimenin tam anlamıyla bir while döngüsü kullanmak zorunda gibi ben bir an önce yazmıştım.
Ancak Pazartesi günü, elimizden iddia verimlilik aleme geri sürüngen
bir şeyi elde logaritmik belki ya da en iyi yine,
var hatta belki de bir şey sabit zaman sözde.
Yani biz bu yeni kullanarak nasıl yapabilirim araçlar, bu adresler, bu işaretçiler,
ve bizim kendi şeyleri parçacığı?
Peki, varsayalım Burada bu bir demet
Biz saklamak istediğiniz sayıların verimli veri yapısı ve arama.
Biz kesinlikle haftaya sarabilirsiniz İki, bir diziye bu atmak
ve ikili arama kullanarak arama yapın.
Bölmek ve fethetmek.
Ve aslında yazdığın PSET3 ikili arama,
nereye bulmak programı uyguladı.
Ama biliyorum.
Daha tür var Bunu yapmanın akılcı bir yoldur.
Biraz daha var Sofistike ve belki de
Bize neden ikili görmenizi sağlar Arama çok daha hızlı böyledir.
İlk olarak, tanıştırayım Bir ağacın kavramı.
Hangi bile olsa gerçeklik ağaçları tür
bilgisayar dünyasında, böyle büyüyecek onlar tür aşağı büyümek bilim
Eğer varsa bir aile ağacı gibi dedesi veya büyük dedesi
veya etajer üst, patrik olarak ve ailenin aile, sadece bir
Kök, düğüm aşağıda denilen onun çocukları olan vardır,
aşağıda onun çocuklarıdır ya torunları daha genel olarak.
Ve herkes asılı etti alt
ağaç, olmanın yanı sıra Ailede genç,
Ayrıca sadece jenerik olabilir Ağacın yaprakları denir.
>> Yani bu sadece bir demet kelime ve tanımları
bir şey için bilgisayarda bir ağaç olarak adlandırılan bilim, bir aile ağacı gibi çok.
Ama meraklısı enkarnasyonlarını var ağaçların, bunlardan biri
İkili arama ağacı denir.
Ve yapabilirsiniz alay tür Bu şey yapar ayrı şey.
Peki, ne anlamda ikili değil mi?
Nereden ikili buraya geliyor?
Maalesef?
O kadar çok bir ya da değil.
Bu düğüm, her hayır vardır daha var İkiden fazla çocuk, burada gördüğünüz gibi.
Genel olarak, bir tree-- içinde ve Ailen ve dedesi
gibi birçok çocuk ya da torun aslında istedikleri gibi,
ve bu nedenle, örneğin orada biz üç var O sağ düğümün kapalı çocuk,
ancak bir ikili ağaç, bir düğüm vardır maksimum, sıfır, bir ya da iki çocuk.
Ve bu, güzel bir özellik var ikisi tarafından kapatılmış oluyor çünkü eğer,
Biz edebilmek için gidiyoruz Biraz günlük tabanı olsun iki
Eylem burada sonuçta oluyor.
Bu yüzden logaritmik bir şey var.
Ama bir anda bu konuda daha fazla.
Arama ağaç numaraları anlamına gelir düzenlenmiş öyle ki sol çocuğun
değer kök büyüktür.
Ve onun sağ çocuk root daha büyük.
Başka bir deyişle, herhangi alırsanız düğümleri, bu resimdeki çevreler,
ve solunda bakar Çocuk ve sağ çocuk
Birincisi, daha az olmalıdır saniyeden daha büyük olmalıdır.
Yani aklı 55 kontrol edin.
Bu çocuğu kalan 33 olduğunu.
O daha az.
55, onun sağ alt 77'dir.
Bu daha büyük bu.
Ve bu özyinelemeli tanımı var.
Biz onlardan her biri kontrol edebilir düğümleri ve yapacağını aynı desen.
>> Yani güzel ne ikili arama ağacı olduğunu
bu bir, biz bunu uygulayabilirsiniz bir yapı ile, sadece bu gibi.
Ve biz atıyorlar bile AT yapıların sürü
Bu veriler bir şekilde konum Sezgisel şimdi umarım.
Sözdizimi, hala emin esrarlı bir ama bu bir düğümün içeriğini
context-- ve biz tutmak Kelime düğümünü kullanarak,
Bir dikdörtgen olsun ekran veya bir daire üzerinde,
o, sadece bazı genel konteyner bulunuyor gibi bir ağaç, bu durumda,
biz bir tamsayı ihtiyacımız gördüm düğümlerin her biri
ve sonra ben iki işaretçileri işaret ihtiyaç Sol çocuk ve sağ çocuğa,
sırasıyla.
Bu yüzden nasıl olabilir bir yapı içinde olduğunu uygulamak.
Ve nasıl kod uygulamak olabilir?
Peki, hızlı atalım Bu küçücük örnek bakmak.
Bu işlevsel değil, ama var Kopyalanan ve bu yapıyı yapıştırılan.
Ve eğer bir ikili benim işlevi arama ağacı, arama denir
ve bu iki argüman alır, bir tamsayı N ve bir işaretçi
ağaç bir düğüm, yani bir işaretçi veya bir ağacın köküne bir işaretçi,
nasıl N ararken gidiyorsun?
Peki, ilk, çünkü ben işaretçileri ile ilgili,
Ben bir sağlamlık denetimi yapmak için gidiyorum.
Ağaç eşittir boş eşitse, N ise Bu ağaçta ya da bu ağacın?
Bu doğru olamaz?
Ben boş geçmiş olsam, Orada hiçbir şey yok.
Ben belki de sadece körü körüne return false söylüyorlar.
Bana hiçbir şey verirsen, ben kesinlikle yapamam herhangi bir sayı N. bulmak başka Yani ne olabilir
şimdi kontrol et?
Ben de başka bir N olup olmadığını söylemek için gidiyorum Ağaç düğümünde ne olursa olsun daha az
Ben N değerini teslim oldum.
Diğer bir deyişle, sayısı eğer ben N, arıyorum, düğümün daha az
Ben bakıyorum söyledi.
Ve düğüm Ben arıyorum Ağaç denir de,
ve önceki örnekte hatırlamak bir işaretçi değeri almak için,
Ben ok gösterimi kullanın.
N ağacı ok daha az Yani N, ben kavramsal sol gitmek istiyorum.
Nasıl sol arıyor ekspres mı?
Bu ise, açık olmak gerekirse Söz konusu resim,
ve ben geçti oldum üstteki olduğunu aşağı işaret ediyor ok.
Bu benim ağaç işaretçi var.
Ben ağacın kökünde işaret ediyorum.
Ve ben, diyelim arıyorum keyfi sayı 44.
Daha küçük veya 44 Açıkçası 55 daha büyük?
Yani daha az.
Ve böylece eğer bu durum geçerlidir.
Yani kavramsal, ben ne istiyorum Ben 44 arıyorum eğer sonraki arama?
Evet?
>> Kesinlikle, ben istiyorum Sol çocuğu arama
ya bu resmin sol alt ağaç.
Ve aslında, geçmeme izin Buraya resim
Sadece bir an için, çünkü Ben bu kazımak olamaz.
Ben 55 burada başlar ve varsa Biliyorum bu değeri 44
Için ben arıyorum Sol, bu tür
içinde telefon rehberini yırtarak gibi Yarım veya yarıda ağaç yırtılma.
Ben artık umurumda zorunda Ağacın tüm bu yarısı.
Ve yine, merakla açısından yapı, burada üzerinde bu şey
, 33 ile başlayan kendisi olduğunu İkili arama ağacı.
Çünkü daha önce kelime özyinelemeli dedi Gerçekten de, bu bir veri yapısıdır olduğu
tanımı gereği özyinelemeli olduğunu.
Bunun olan bir ağaç olabilir büyük, ama onun çocuklarının her biri
küçük biraz bir ağacı temsil eder.
Bunun yerine büyükbaba olmak ya da büyükanne, şimdi sadece anne
yoksa-- ben anne değil say-- olamaz ya da baba, bu garip olurdu.
Orada yerine iki çocuk kardeşi ve kardeş gibi olurdu.
Aile ağacı yeni nesil.
Ama yapısal, aynı fikir.
Ve ben bir işlevi var çıkıyor hangi ile ben bir ikili arama arama yapabilirsiniz
ağaç.
Bu arama denir.
Ben ağaç ok sol N arama N değerinden büyükse else if
ben şu anda değilim.
Bir an önce hikaye 55.
Ben adında bir işlevi var arama ben sadece can
N bu geçmek ve özyinelemeli arama alt ağacı ve adil dönüş
ne olursa olsun cevap.
Else Burada bazı nihai taban dava var.
>> Son durum nedir?
Ağaç ya null.
Ben de arıyorum değeri bundan daha az ya da daha fazla
ya da eşit.
Ve ben eşit söyleyebiliriz eşit, ancak mantıksal olarak bu kadar
Sadece burada başka söyleyerek eşdeğer.
Yani gerçek bir şey bulmak nasıl olduğunu.
Yani umarım bu bir olduğunu daha zorlayıcı bir örnek
Aptal sigma fonksiyonu daha Biz bir kaç dersler yaptım
nerede bir döngü kullanımı gibi kolay birinden bütün numaralarını saymak
Bir veri yapısı ile Burada N'ye kendisi, yinelemeli olduğu
biz şimdi, tanımlanmış ve özyinelemeli çizilmiş kendimizi ifade yeteneğine sahip
kod kendisi özyinelemeli olduğunu.
Yani bu burada aynı kodudur.
>> Yani biz ne diğer sorunlar çözebilir?
Uzağa Yani hızlı bir adım Sadece bir an için ağaçlar.
İşte isimli, Alman bayrağı söylüyorlar.
Ve açıkça orada bir Bu bayrak desen.
Ve bir sürü var Dünyada bayraklar o
açısından bu kadar basit Onların renk ve desen.
Ama bu olarak saklanır varsayalım .GIF Veya JPEG veya bitmap veya ping,
herhangi bir grafik dosyası biçimi hangi ile, aşina
Biz konum bazıları PSET4 içinde oynamaktan.
Bu saklamak için değerli görünmüyor siyah piksel, siyah piksel, siyah piksel,
nokta, nokta, nokta, bir sürü İlk scanline siyah pikseller,
veya satır, daha sonra bir sürü Aynı sonra bir sürü
Daha sonra, aynı, ve Kırmızı piksel sürü,
kırmızı piksel, kırmızı piksel, daha sonra bir bütün Sarı sarı piksel demet, değil mi?
>> Böyle verimsizlik var burada.
Nasıl sezgisel olur Alman bayrağı sıkıştırmak
Bir dosya olarak uygulanması durumunda?
Hangi bilgileri gibi biz yapamam sırayla diskte saklamak rahatsız
gibi bizim dosya boyutunu azaltmak için Bir kilobayt, bir şey, bir megabayt
Daha küçük?
Buradaki fazlalık yatıyor Burada açık olması?
Ne yapabilirdi?
Evet?
Kesinlikle.
Neden yerine hatırlıyorum Her lanetlemek pikselin rengi
sadece PSET4 içinde yapıyoruz gibi Bitmap dosya formatı ile,
neden sadece temsil etmemektedir Örneğin piksel soldaki sütun,
siyah pikseller bir demet, bir demet kırmızı, sarı ve bir demet,
ve sonra sadece her nasılsa kodlamak tekrar fikri bu 100 kez
ya bu 1000 kez tekrarlayın?
Nerede 100 veya 1.000 Sadece bir tamsayı, sana bu yüzden
sadece tek bir numara ile kurtulabiliriz Bunun yerine yüzlerce ya da binlerce
ek piksel.
Ve gerçekten de, bu nasıl biz var Alman bayrağı sıkıştırmak olabilir.
Ve
Fransız bayrağı hakkında şimdi ne olacak?
Bazı tür ve biraz zihinsel egzersiz, hangi bayrak
diskte daha fazla sıkıştırılmış olabilir?
Alman bayrağı veya Fransızca bayrak, biz bu yaklaşım olur?
Alman bayrağı, var, çünkü daha yatay fazlalık.
Ve tasarım, çok sayıda grafik dosya biçimleri gerçekten de tarama çizgileri çalışır
yatay.
Onlar işe yarayabilir dikey, sadece insanlık
karar yıl önce yaparız Genellikle işler satır düşünüyorum
kolonu ile satır yerine kolonu ile.
Yani gerçekten sen olsaydın dosyaya bakmak için
Bir Alman bayrağı ve Fransızca boyutu bayrak, bu kadar uzun çözünürlüğü olarak
Aynı, aynı genişlik ve yükseklik bu
Burada, daha büyük olacak çünkü sen Kendinize üç kez tekrarlamak zorunda.
Mavi, tekrarı belirtmek zorunda Kendinizi, beyaz, kırmızı, kendinizi tekrar
Kendinizi tekrarlayın.
Sadece tüm gidemez sağa yolu.
Ve bir kenara olarak, yapmak sıkıştırma temizlemek
Bu ise, her yerde Bir video-- dört çerçeveler
Bir film olduğunu hatırlamak olabilir ya da video genellikle
saniyede 29 veya 30 kare gibi.
Biraz flip kitap gibi nerede Sadece görüntü, resim, görüntü, görüntüyü görmek,
Görüntü sadece süper hızlı bu yüzden gibi görünüyor Ekrandaki aktörlerin hareket ediyor.
İşte arı üzerinde bulunuyor bir demet çiçek üst.
Ve bu tür olabilir ama ilk bakışta görmek zor,
hareket tek şey Bu film arı olduğunu.
>> Ne depolama hakkında aptal Video sıkıştırılmamış?
Bu Videoyu saklamak için bir atığın tür Dört neredeyse aynı görüntü olarak o
Sadece ölçüde arı olduğu kadar farklıdır.
Sen uzağa atabilir çoğu bu bilginin
ve tek unutmayın, örneğin, İlk kare ve son kare,
Eğer yasiyorsaniz anahtar kare Hiç, kelime duymadım
ve sadece saklamak arı olan orta.
Ve gerek yok , pembe tüm mağaza
mavi ve ve Yeşil değerler de.
Yani bu sadece demek ki sıkıştırma her yerde.
Biz sık sık kullandığımız bir tekniktir bu gün için verilen veya almak.
>> Ama nasıl metin sıkıştırmak mı?
Nasıl metnin sıkıştırılması gidiyorsun?
Eh, karakterlerin her ASCII bir byte veya sekiz bittir.
Ve bu tür aptal, haklı?
Muhtemelen A tipi nedeniyle ve E ve ben ve O ve U çok
daha sık W ya da Q ya da Z gibi daha dile bağlı olan
kesinlikle yazıyoruz.
Ve böylece neden kullanıyorsunuz Her harf için sekiz bit,
En az olmak üzere popüler mektuplar, değil mi?
Neden için daha az bit kullanmak süper popüler harfler,
E gibi, şeyler sanırım İlk Wheel of Fortune olarak,
ve daha fazla bit kullanımı az popüler mektuplar?
Neden?
Biz sadece gidiyoruz çünkü daha az sıklıkla kullanıyorum.
>> Peki, orada var olduğu ortaya çıkıyor Bunu yapmak için yapılan girişimler olmuştur.
Ve notu çağırmak durumunda okul ya da lise, Mors kodu.
Mors kodu noktalar var ve çizgiler olabilir
bir tel gibi boyunca iletilen sesler ya da bir tür sinyaller.
Ama Mors kodu süper temiz.
Bu bir ikili sistemin tür Bu sizi noktalar veya tire var.
Ama, örneğin, iki nokta görürseniz.
Ya da operatöre geri düşünüyorsanız kim, bip, bip, bip sesi gibi gider
bip biraz tetik isabet bir sinyal gönderir,
eğer alıcı, iki alır noktalar ne mesaj aldınız?
Tamamen keyfi.
>> BEN?
BEN?
Ya da ne about-- ya da ben?
Belki de sadece iki E'nin haklıydı?
Yani bu sorun var Morse ile decodability arasında
Kod, bu sayede sürece Size mesaj göndererek kişi
aslında bunu size sıralayabilirsiniz duraklar bakın veya harfler arasındaki boşlukları duymak,
Sadece yeterli değil sıfırlar ve olanları bir akışı göndermek,
veya noktalar ve tire, belirsizlik var çünkü.
E bir tek nokta, bu yüzden eğer İki nokta görmeniz ya da iki nokta duymak,
belki de iki E'nin var ya da belki tek I. var
Yani bir var bir sisteme ihtiyacımız var Bundan daha zeki küçük.
Yani bir erkek adında Huffman yıllar önce tam olarak bu ile geldi.
Yani biz sadece gidiyoruz hızlı bir bakış almaya
Nasıl ağaçlar bu germane bulunmaktadır.
Bu, bazı olduğunu varsayalım Göndermek istediğiniz aptal mesajı
Sadece A, B oluşan C'nin D'nin ve E'nin, ancak fazlalık Burada bir sürü var.
Bu İngilizce olması gerekiyordu değil.
Bu şifreli değil.
Sadece aptal bir mesaj var tekrar bir sürü ile.
Aslında saymak Yani tüm A takımından, B, C kıyafetleri, D'nin, ve E'nin, burada
sıklığı.
Harflerin% 20 Bir kıyafetleri, mektupları% 45
E'nin, ve diğer üç frekansları vardır.
Biz el orada sayılır ve sadece matematik yaptım.
>> Bu yüzden çıkıyor Huffman, bir süre önce,
bilirsin, fark Ne ben binayı başlatırsanız
Bir ağaç veya ağaçlar orman, eğer sen, aşağıdaki gibi, ben aşağıdakileri yapabilirsiniz.
Her bir düğüm vereceğim Ben umurumda harflerin
ve ben saklamak için gidiyorum bu düğüm içinde
Bir kayan nokta olarak frekansları değer veya siz de bir N-ebil kullanma
ama biz sadece burada bir şamandıra kullanacağız.
Ve algoritma o senin olduğunu önerdi
tek bir düğüm bu ormanı almak ağaçlar, bu yüzden süper kısa ağaçlar,
ve onları bağlayan başlamak yeni gruplar, yeni anne-babalar, eğer sen.
Ve seçerek bunu Bir anda iki küçük frekansları.
Yani% 10 ve% 10 aldı.
Ben yeni bir düğüm oluşturun.
Ve ben yeni düğüm% 20 diyoruz.
>> Hangi iki düğüm sonraki birleştirmek?
Biraz belirsiz bu.
Yani bazı köşe durumlarda var düşünün, ama güzel şeyleri tutmak için,
Ben% 20 seçmek için gidiyorum - Ben şimdi çocukları görmezden.
Ben% 20 seçmek için gidiyorum ve % 15 ve iki yeni kenarlar çizin.
Ve şimdi hangi iki düğüm Ben mantıklı birleştirmek?
Tüm çocukları, tüm Ignore torunları, sadece köklerine bakmak
şimdi.
Hangi iki düğüm Birlikte kravat mı?
İkinci nokta ve 0.35.
Bu yüzden bana iki yeni kenarlar çizelim.
Ve sonra ben yalnızca bir sol var.
Yani burada bir ağaç.
Ve kasten çizilmiş oldu tür güzel bakmak,
ama kenarları olduğunu fark Ayrıca sıfır ve bir etiketlendi.
Yani sol kenarları tümü sıfır keyfi, ama sürekli.
Tüm doğru kenarları olanlardır.
>> Ve böylece Hoffman, isimli önerisi ile Bir B temsil etmek istiyorsanız,
Numarayı 66 temsil yerine Sekiz tüm bit bir Ascii,
ne sadece mağaza biliyorum desen sıfır, sıfır, sıfır,
Sıfır bu yolu var, çünkü Benim ağacından Sayın Huffman ağacı,
kökünden yaprak.
Bir saklamak istiyorsanız E, aksine, yapma
Bir E. temsil eden sekiz bit göndermek Bunun yerine, bit ne desen göndermek?
Bir.
Ve bu konuda güzel ne Bu E en popüler mektup,
ve kullandığınız Bunun için en kısa kodu.
Bir sonraki en popüler mektup öyle görünüyor
A. oldu Ve böylece kaç bit o için kullanıyor teklif mi?
Sıfır, bir.
>> Ve bu uygulamaya çünkü Bu ağaç gibi, şimdi
Benim orada şart izin Morse hiçbir belirsizlik
kod, tüm çünkü önemsediğiniz mektuplar
Bu kenarlarda sonundadır.
Yani bu sadece biri Bir ağacın uygulaması.
Bu bu-- ve ben dalga edeceğiz Bu benim eli nasıl
bir Cı-yapı olarak, bu uygulayabilir.
Biz sadece birleştirmek gerekiyor Bir sembol, bir char gibi,
ve frekans sol ve sağ.
Ama iki bakalım Son örnekler olacak
sonra oldukça tanıdık olsun problem yarışması sıfır beş set.
>> Yani veri yapısı var karma tablo olarak da bilinir.
Ve bir karma tablo tür bir o kovalar sahip olması serin.
Ve dört kova var varsayalım Burada, sadece dört boşluk.
İşte burada olduğu kartların bir güverte ve Kulüp, kürek, kulüp, elmas, kulüp,
elmas, kulüp, elmas, clubs-- nedenle bu rastgele.
Kalpler, hearts-- yüzden ben Burada tüm giriş uçlarını bucketizing.
Ve bir karma tablo ihtiyaçları senin girdi bakmak için,
ve daha sonra belli bir koyun Gördüğünüz ne dayalı yerleştirin.
Bu bir algoritma var.
Ve ben bir süper kullanıyordum Basit bir görsel algoritma.
En zor kısmı oldu Resimler ne olduğunu hatırlayarak.
Ve sonra toplam dört şey var.
>> Şimdi yığınlar, büyüyen hangi Burada kasıtlı tasarım şeydir.
Ama başka ne olabilir?
Yani aslında burada var bir eski okul sınav kitaplarının demet.
Bir demet Varsayalım ki Öğrenciler isimler burada bulunmaktadır.
İşte büyük bir karma tablo var.
Yerine dört kovalar, Ben, en 26 diyelim var.
Ve biz 26 ödünç gitmek istemiyordu dış [gelen şeyler? Annenberg?], Bu yüzden
Burada temsil beş var A'dan Z'ye aracılığıyla Ve ben
, adı A ile başlayan bir öğrenci bakın Orada onun ya da onu sınavı koymak için gidiyorum.
Birisi C başlarsa, orada, A- aslında bunu yapmak istemiyordu.
B buraya gidiyor.
Yani var A ve B ve C Ve şimdi burada başka bir öğrencisi.
Ama bu karma tablo ise bir dizi ile uygulanan
Ben biraz berbat ediyorum Bu noktada, doğru mu?
Ben biraz bu bir yere koymak gerekir.
>> Yani bu çözebilir tek yolu tüm olup Doğru, A, C meşgul, B meşgul, meşgul.
Ben Yani D. onu koymak için gidiyorum İlk, ben rastgele anında erişim var
Öğrenciler için kovalar her.
Ama şimdi bu tür intikal ediyor şey doğrusal içine
Ben kimse için aramak istiyorsanız, çünkü kimin adı A ile başlayan, ben burada kontrol edin.
Ancak bu bir değilse Ben arıyorum, öğrenci,
Tür kontrol başlamak zorunda kovalar, ben ne yaptım çünkü
arasında doğrusal sıralama oldu veri yapısını soruşturma.
Sadece bakmak söyleyerek bir aptal yolu İlk kullanılabilir açılması için,
ve, tabiri caizse, bir B planı olarak koymak veya bu durumda planın D, değer
Bunun yerine bu konumda.
Bunun anlamı, yasiyorsaniz sadece bu yüzden olduğunu 26 yerleri ve hiçbir öğrencileri var
adı Q veya Z, falan gibi olan Bu, en azından alanı kullanarak ediyoruz.
>> Ama biz zaten daha gördüm Burada zeki çözümler, değil mi?
Bunun yerine ne yapardın Eğer bir çarpışma varsa?
Iki kişi varsa, adı A, ne istiyorsunuz
daha akıllı ya da daha fazla olmuştur Sadece daha kolay çözüm
D olması gerekiyordu A koyarak?
Neden sadece gitmeyin dış [? Annenberg?]
malloc, başka bir düğüm gibi, koyun Burada ve daha sonra burada bir öğrenci koymak.
I esas sahip böylece Bir dizinin çeşit,
ya da konum olarak belki daha zarif Bağlantılı bir listesini görmek için başlıyor.
>> Ve böylece bir karma tablo bir yapıdır Bu, sadece bu gibi görünebilir
ama daha akıllıca, sen bir şey denir Ayrı zincirleme, böylece bir karma tablo
oldukça sade bir dizi her biri olduğunu olan elemanları bir sayı değil,
bağlantılı liste kendisidir.
Süper hızlı erişim olsun, böylece Nerede sizin değer karma karar.
Çok kartlar örnek gibi, Ben süper hızlı kararlar.
Kalpler elmas buraya, buraya.
Aynı burada, A buraya, D B buraya, buraya.
Yani süper hızlı look-up ve eğer Eğer bir durumda rastlıyorum
Eğer var çarpışmalar, iki Aynı isimde insanlar, iyi o zaman
Sadece bunları birbirine bağlayan başlar.
Ve belki onları kriteri tutmak alfabetik, belki yok.
Ama en azından şimdi dinamizm var.
Yani bir taraftan biz süper hızlı olması sabit zaman ve lineer zamanın tür
Bu bağlantılı listeler halinde yer biraz uzun olsun başlar.
>> Yani bir aptal bu tür Önce geeky şaka yıl.
CS50 kesmek-a-thon anda, Öğrenciler iade ettiğinizde,
Bazı TF veya CA, her yıl düşünüyor o kadar koymak komik
Böyle bir işaret, nerede o sadece Adın bir A ile başlıyorsa eğer gelir,
Bu şekilde gitmek.
Adın başlarsa Bir B, bu-- Tamam gidin,
belki daha sonra yarıyılda komik.
Ama başka bir var da bunu yapmanın yolu.
Geri o gel.
>> Yani bu yapı var.
Ve bu bizim son bir Bugün için yapı,
hangi bir tray denilen şeydir.
Herhangi bir nedenle kısa bir T-R-I-E, alımı için, ancak tray denir.
Bu nedenle bir tray bir ilginç Bu fikirlerin bir sürü amalgam.
Biz daha önce gördüğümüz bir ağaç, var.
Bu ikili arama ağacı değil.
Bu, çocukların herhangi bir sayı ile bir ağaç var ancak tray çocuk her
bir dizidir.
Boyut dizisi, 26 ya da belki 27 say Eğer hyphenated isimleri desteklemek istiyorsanız
veya insanların isimleri kesme.
>> Ve bu nedenle bu, bir veri yapısıdır.
Ve yukarıdan bakarsanız alt, gibi eğer
, orada üst düğüm, M bakmak Orada soldaki şey işaret ederek,
bu daha sonra, A, X, W, E, L, L Bu edilir Sadece bir veri yapısı olduğunu keyfi
insanların isimlerini saklamak olduğunu.
Ve Maxwell sadece takip ederek depolanır diziye diziye dizinin bir yol.
Bir tray ilgili ama şaşırtıcı ne Bu bir bağlantılı liste ise ve hatta
Bir dizi, biz şimdiye kadar kazanılmış en iyisidir lineer zaman ya da logaritmik zaman seyir
Birisi yukarı.
Bir tray Bu veri yapısı, eğer içinde Benim veri yapısı içinde bir isim var
ve ben Maxwell arıyorum, ben oldukça hızlı onu bulmak için gidiyor.
Ben sadece M-A-X-W-E-L-L arayın. Eğer Bu veri yapısı, aksine,
Bir varsa N, bir milyon ise Bu veri yapısı milyon isimleri
Maxwell hala olacak keşfedilebilir sadece M-A-X-W-E-L-L sonrası
adımlar.
Ve David-- D-A-V-I-D adımları.
Diğer bir deyişle, bina olan bir veri yapısı
var olan bu dizilerin hepsi, her biri kendileri, rastgele erişim desteği
İnsanların 's bakarak başlayabilirsiniz bu süre bir miktar kullanarak isim
değil sayısı ile orantılı veri yapısı şeyler,
gibi bir milyon varolan isimler.
Bulmak beni alır süre M-A-X-B-E-L-L Bu veri yapısı içinde
orantılı değil veri yapısının boyutu,
ama adının uzunluğuna.
Ve gerçekçi isimler biz arıyoruz
Asla uzun deli olacak.
Belki birisi 10 karakteri vardır 20 karakter ismi.
Bu doğru, kesinlikle sonlu değil mi?
Yeryüzünde insan vardır kim mümkün olan en uzun ada sahip,
ama bu isim bir sabittir değer uzunluğu, değil mi?
Bu, herhangi bir anlamda farklılık yoktur.
Bu yüzden, bu şekilde, biz ettik Bir veri yapısı elde
O zaman sabiti look-up olduğunu.
Bu bir dizi adım sürer giriş uzunluğuna bağlı olarak,
isim değil numara veri yapısı içinde.
Biz isimlerin sayısını iki katına Yani eğer Bir milyar iki milyar ila gelecek yıl,
bulgu Maxwell sürecekse Yedi adım aynı sayıda
Onu bulmak için.
Ve böylece biz elde ettik görünüyor çalışma süresi bizim kutsal kasesi.
>> Yani hızlı duyurular bir çift.
Sınav sıfır geliyor.
Dersin web sitesinde bu konuda daha fazla önümüzdeki birkaç gün boyunca.
Pazartesi günü bir bayram var lecture-- Burada Harvard'da Pazartesi günü.
Bu, New Haven değil bu yüzden sınıf alıyoruz
Pazartesi günü ders için New Haven.
Herşey çekilecek ve her zamanki gibi canlı akış
ama en sonunda bugün edelim 30 saniyelik bir klip ile
sözde "Derin Düşünceler" Daven Farnham tarafından hangi
Cumartesi geçen yıl esinlenilmiştir Gece Live'ın "Derin Düşünceler"
Jack Handy tarafından hangi Şimdi mantıklı olmalıdır.
>> FİLM: Ve şimdi, "Derin Daven Farnham tarafından Düşünceler ".
Hash tablo.
>> KONUŞMACI 1: Pekala, o an için bu.
Gelecek hafta görüşürüz.
>> Doug: eylem görmek için.
Yani şimdi o bir göz atalım.
Yani burada biz bir sıralanmamış dizi var.
>> IAN: Doug, önde ve yeniden gidebilir Sadece bir saniye için bu, lütfen.
Pekâlâ, kameralar, yani haddeleme eylem Doug, hazır olduğunda, tamam mı?
Doug: Pekala, ne Burada var bir sıralanmamış dizidir.
Ve ben bütün elemanları renkli ettik aslında olduğunu göstermek için kırmızı,
unsorted.
Yani ilk şey yaptığımız hatırlamak biz dizi sol yarısını sıralamak olduğunu.
Sonra sağa sıralamak Dizinin yarısı.
Ve ya-da, ya-da, ya-da, Beraber onları birleştirmek.
Ve biz tamamen sıralı dizi var.
Yani işler birleştirmeli sıralama nasıl.
>> IAN: dur, dur, dur, kes, kes, kes, kes.
Doug, sadece ya-da olamaz, ya-da, ya-da, birleştirme sıralama yolumuzu.
>> Doug: ben yaptım.
Bu iyi.
Biz gitmek için iyi bir konum.
Sadece haddeleme tutalım.
Her neyse,
>> IAN: Sen açıklamak zorunda daha tam olarak bundan daha.
Bu sadece yeterli değil.
Doug: Ian, biz değiliz birine geri gitmek gerekir.
Bu iyi.
Neyse, biz merge-- ile devam edersek Ian biz filme ortasındayız.
>> IAN: Biliyorum.
Ve biz sadece ya-da olamaz, ya-da, tüm süreç boyunca ya-da.
Sen nasıl açıklamak zorunda İki taraf birbirine birleştirilir.
>> Doug: Ama biz zaten ettik açıkladı nasıl iki sides--
>> IAN: Sadece gösterilen ettik Onları bir birleştirme dizisi.
Doug: Onlar süreci biliyorum.
Onlar iyi.
Biz bunun üzerine on kez gittim.
>> IAN: Sadece sağ atlanır.
Biz bir geri gidiyoruz, sen Bunun üzerine sen ya-da, ya-da yapamam.
Geri birine tamam.
>> Doug: Ben geri gitmek zorunda Slaytlar arasında durmadan?
Tanrım.
Bu altıncı kez, Ian gibi.
Bu iyi.
>> IAN: Pekala.
Hazır mısın?
Büyük.
Eylem.