Doug LLOYD: Yani CS50 olarak, biz kapalı ettik Farklı veri yapılarının bir sürü sağ? Biz diziler gördük, ve bağlantılı ettik listeleri ve hash tabloları, ve çalışır, yığınlar ve kuyruklar. Biz de biraz öğreneceksiniz ağaçlar ve kümeler hakkında, ama gerçekten bunlar hepsi sadece bitirmek yukarı bir tema üzerine varyasyonlar olmak. Gerçekten var bu dört temel fikirlerin tür Başka her şeyi aşağı kaynatın. Diziler, bağlı listeler, hash tabloları ve çalışır. Ve gibi orada, dedi onlara varyasyonları vardır, ama bu güzel çok özetlemek olacak Her şey biz konuşacağız C bakımından bu sınıf ile ilgili olarak Ama nasıl bu doğru, her ölçü kadar mı? Biz artılarını ve eksilerini hakkında konuştuk onlara ayrı videoları her, ancak sayıların çok şey var etrafında atılan alıyorum. Genel bir sürü var düşünceler etrafında atılan alıyorum. Denemek ve konsolide edelim Sadece tek bir yerde. En karşı artılarını tartmak edelim Eksileri ve düşünün bu veri yapısını doğru veri olabilir Size özel durum için yapı, Verilerin ne tür depolama ediyoruz. Sen mutlaka her zaman gerekmez süper hızlı ekleme, silme kullanın Bir tray ve arama eğer gerçekten ekleme ve silme umurumda değil çok fazla. Sadece hızlı rastgele gerekiyorsa erişim, belki bir dizi daha iyidir. Yani bu damıtmak edelim. En dört her biri hakkında konuşalım veri yapılarının önemli türlü Konuştuğumuz ve ettik Onlar iyi olabilir zaman sadece görmek, ve ne zaman onlar kadar iyi olmayabilir. Yani diziler ile başlayalım. Ekleme Yani, biraz kötü. 

Bir dizinin sonuna ekleme, Tamam Biz giderken biz bir dizi inşa ediyorsanız. Ama biz eklemek gerekirse ortasına elemanları, ekleme geri düşünmek sıralama, bir çok şey var orada bir eleman sığacak şekilde kayması. Ve biz eklemek için gidiyoruz eğer öyleyse Her yerde ama bir dizi sonu muhtemelen çok büyük değil. 

Benzer şekilde, silme, sürece biz konum Bir dizinin sonundan silme, belki de bu yüzden büyük değil Biz boş boşluklar bırakmak istemiyorum, hangi genellikle biz değil. Biz bir öğe kaldırmak istiyorsanız, ve Daha sonra sıralama tekrar rahatını olun. Ve böylece öğeleri silme Bir dizi, aynı zamanda çok büyük değil. 

Arama olsa da, harika. Biz rastgele erişim, zaman sabiti arama. Biz sadece yedi demek, ve biz gitmek Dizi tehcir yedi. Biz gitmek ile, 20 say Dizi tehcir 20. Biz genelinde yineleme gerekmez. Bu oldukça iyi. 

Diziler de sıralamak nispeten kolaydır. Biz sıralama hakkında konuştuk Her zaman Böyle seçim tür olarak algoritma, Ekleme sıralama, kabarcık sıralama, birleştirme sıralama, her zaman bunu yapmak için diziler kullanılır, diziler oldukça kolay, çünkü veri yapıları göreli sıralama, Şimdiye kadar gördüğüm. 

Onlar da nispeten küçük konum. Ekstra alan bir şey yok. Sadece tam olarak çok kenara Verilerinizi tutmak gerekir gibi, ve bu oldukça fazla. Yani oldukça küçük olduğunu ve bu şekilde etkili. Ama başka bir dezavantajı olsa da, büyüklüklerinin sabit olmasıdır. Biz tam olarak nasıl beyan etmek zorunda Büyük biz bizim dizi olmak istiyorum ve biz sadece ona bir tane vurulmaz. Biz büyümek ve bunu küçültmek olamaz. 

Biz büyümek ya da küçültmek için gerekiyorsa, biz tamamen yeni bir diziyi bildirmek gerekiyor unsurlarının kopyalayın İkinci diziye ilk dizi. Ve biz bu yanlış hesap varsa zaman, biz tekrar yapmak gerekiyor. Kadar büyük değil. Yani diziler bize esneklik vermeyin elementlerin değişken numaraları için. 

Bağlı liste ile, ekleme oldukça kolaydır. Biz sadece ön yüzüne çakmak. Silme da oldukça kolaydır. Biz unsurları bulmak zorundayız. Bu bazı arama içerir. 

Ama eleman bulduktan sonra Eğer yapmanız gereken, tüm arıyoruz bir işaretçi değiştirmek olduğunu, muhtemelen iki varsa Bir çifte list-- bağlanmış bağlantılı liste, rather-- ve sonra sadece düğüm ücretsiz yapabilirsiniz. Sen kaydırmaya gerek yok etrafında her şey. Sadece, iki işaretçileri değiştirin böylece oldukça hızlı. 

Arama doğru olsa kötü mü? Bize bir bulmak için için Bağlantılı bir listede elemanı olup tek veya iki bağlantılı biz bunu arama doğrusal gerekiyor. Biz başında başlamak zorunda ve ucunu hareket ettirmek, ya da son hareket başlatmak başlangıcına. Artık rastgele erişim yok. Biz yapıyoruz, bu yüzden arama sürü, belki bağlantılı liste değildir Bizim için o kadar iyi. 

Onlar gerçekten de konum sıralamak zor, değil mi? Tek yolu yapabilirsiniz Gerçekten bağlantılı listeyi sıralamak Bunu inşa olarak sıralamak etmektir. Ama senin gibi sıralamak eğer Bunu inşa, artık değilsin Artık hızlı eklemeleri yaparak. Sadece teyel değil Ön üzerine işler. Sen bulmak zorunda Doğru nokta koymak için, ve sonra ekleme sadece yaklaşık olarak kötü olur bir diziye ekleme gibi. Yani bağlı listeler değil veri sıralama için çok büyük. 

Onlar da oldukça küçük, boyut-bilge değilsin. Çifte biraz listesi bağlantılı tek başına bağlantılı listeler daha büyük, bu biraz daha büyüktür diziler daha, ama bu değil israf alanı büyük miktarda. Yani uzay prim, ama değil gerçekten yoğun bir prim, bu gitmek için doğru yol olabilir. 

Hash tablo. Karma tabloya Yerleştirme oldukça basittir. Bu iki aşamalı bir süreçtir. İlk aracılığıyla veri çalıştırmak için gereken Bir hash fonksiyonu bir karma kodu almak için, ve sonra içine öğe eklemek Bu karma kodu yerde karma tablo. 

Bağlantılı listeye benzer Silme, Eğer eleman bulduğunuzda kolaydır. Sen önce onu bulmak zorunda ama sonra bunu sildiğinizde, Sadece alışverişi gerekir işaretçiler bir çift, Eğer ayrı zincirleme kullanıyoruz. Eğer sondalama kullanıyorsanız, ya sen değilsin eğer kullanarak tüm zincirleme senin hash tablosunda, silme aslında gerçekten çok kolay. Yapmanız gereken tek şey karma olduğunu Veri ve o konuma gidin. Ve varsayarak değil mi Herhangi bir çarpışmalar Çok hızlı bir şekilde silmek mümkün olacak. 

Şimdi, arama nerede şeyler Biraz daha karmaşık olsun. Daha iyi ortalama var bağlantılı listeler daha. Eğer zincirleme kullanıyorsanız, Hala bir bağlantılı liste var, hangi hala var demektir Arama bağlantılı liste zarar veren. Eğer alıyorsun çünkü senin bağlantılı listesi ve 100 veya 1000 üzerinde bölme veya n da karma tablo elemanları, sen bağlı listeler boyutu inci hepsi biridir. Hepsi önemli ölçüde daha küçük olduğunu. Sen n yerine listeleri bağladığınız n büyüklüğünde bir bağlantılı liste. 

Ve böylece bu gerçek dünya sürekli Genellikle biz faktörü, Zaman karmaşıklığı hakkında konuşmak yok, o Aslında burada bir fark yoktur. Yani arama hala doğrusal Eğer zincirleme kullanıyorsanız arama ancak listenin uzunluğu Üzerinden aradığınız kıyasla çok kısadır. Yine, sınıflandırıp ise, Burada amaç, karma tablo en Muhtemelen doğru yolu gitmek için değil. Sıralama eğer sadece bir dizi kullanmak Sizin için çok önemli. 

Ve onlar büyüklük gam çalıştırabilirsiniz. Bir olmadığını söylemek zor hash tablosu, küçük ya da büyük Gerçekten bağlıdır çünkü ne kadar büyük senin karma tablodur. Sadece depolamak için gidiyoruz senin hash tablosunda beş element, ve bir karma tablo var İçinde 10.000 elemanları ile, muhtemelen çok yer harcıyorsun. Kontrast ayrıca yapabilirsiniz olmak , çok kompakt hash tabloları var ama daha küçük senin hash tablosu, gets Bu bağlantılı listeler, her uzun alır. Ve bu yüzden gerçekten tanımlamak için hiçbir yolu yoktur Tam bir karma tablosu boyutu ama muhtemelen güvenli genellikle söylemek Bağlantılı daha büyük olacak Aynı veri depolama listesi, Bir tray daha ancak daha küçük. 

Ve çalışır dördüncü olan Bu yapıların biz bahsediyoruz oldum. Bir tray takmadan karmaşıktır. Dinamik bir sürü var bellek ayırma, Özellikle başında, inşa etmek başlıyoruz olarak. Ama sürekli zamanı. Bu sadece insan unsuru var Burada zor hale getirdiğini. Null işaretçi karşılaşmaya olması, malloc uzay, muhtemelen malloc uzay oraya gitmek Oradan tekrar. Sindirme faktörü tür dinamik bellek tahsisi işaretçileri temizlemek için engeldir. Ama bunu bir kez temizlenir, ekleme aslında oldukça basit geliyor ve kesinlikle sabit zamanıdır. 

Silme kolaydır. Yapmanız gereken tek şey aşağı gezinmek bir işaretçiler ve ücretsiz düğümün çift, böylece oldukça iyi. Arama da oldukça hızlı. Sadece tabanlıdır verilerinizin uzunluğu. Tüm verilerinizi Yani eğer Beş karakter dizeleri, Örneğin, beş saklıyoruz senin tray karakter dizeleri, sadece beş adımlar atması Eğer aradığınızı bulacaksınız. Beş yüzden, sadece sabit bir faktördür Yine, ekleme, silme ve arama Burada etkili tüm sabit zaman vardır. 

Başka bir şey tray olduğunu aslında tür zaten sağ sıralanır? Biz konum nasıl sayesinde ekleme elemanları, bir harfi giderek anahtarın rakamı ile anahtar veya rakam, genellikle, senin tray olmak biter Bunu kurmak gibi tür sıralanır. Gerçekten yapar değil duygusu sıralama düşünmek aynı şekilde biz düşünmek bu diziler, veya bağlantılı listeleri, veya karma tablolar. Ancak bazı anlamda, sizin Eğer gitmek gibi tray sıralanır. 

Olumsuz, tabii ki, yani bir tray hızlı büyük hale gelir. Her kavşak noktadan itibaren, belki anahtar rakamlardan oluşuyorsa have--, Diğer 10 var yerleştirir, gidebilirsin ki Her düğümün demektir bilgi içerir veriler hakkında Saklamak istediğiniz bu düğüm, artı 10 işaretçileri de. Hangi CS50 IDE, 80 bayt. Bu yüzden en az 80 bayt var Oluşturduğunuz her düğüm, ve hatta veri sayma değil. Ve düğümler ise yerine basamak mektupları, şimdi 26 işaretçiler var Her yerden. Ve 26 kat 8 muhtemelen 200 bayt, ya da onun gibi bir şey. Ve sermayeye sahip ve size yapabilirsiniz lowercase-- Ben bu ile gidiyorum nereye doğru, gördün mü? Sizin düğümler gerçekten alabilirsiniz Büyük ve böylece tray kendisi, genel olarak, can çok gerçekten büyük olsun. Uzay yüksek olan yani eğer Sisteminizde prim, Bir tray doğru yol olmayabilir Hatta onun diğer faydaları olsa da, gitmek oyuna gel. Ben Doug Lloyd değilim. Bu CS50 olduğunu.