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.