[MÜZİK OYUN]
>> David MALAN Bu CS50 olup.
Ve bu başlangıç ​​ve hem gerçekten-- neredeyse sonu gibi end--
Haftanın altı.
>> Ben paylaşmak düşündüm eğlenceli aslında biraz.
Ben bir bu kadar çekti ettik Geçtiğimiz dönemlik veri seti.
Sen her sizi sormak Hatırlayacağınız p seti formu online izledim eğer
veya bizzat katıldı ettik.
Ve burada veridir.
Yani bugün çok öngörülebilir.
Ama biz biraz harcamak istedim zaman sizinle yine.
Herkes neden bu varsayım ister misiniz grafik, yukarı aşağı, yukarı aşağı, yani çentikli olan
bu yüzden sürekli?
Ne zirveleri her do ve olukları temsil?
>> İZLEYİCİ: [Duyulmaz]
DAVID MALAN: Gerçekten.
Ve daha eğlenceli, tanrı korusun, Biz Cuma günü bir ders tutun
dönem başında, biz ne bkz ne.
Yani bugün, biraz paylaşmak veri yapıları hakkında daha fazla.
Ve sana bir katı fazlasını vermek beşte sorunlar için zihinsel modeli,
hangi şimdi dışarı.
Yazım olup, burada, yaparız Size bir metin dosyası el 100.000
artı İngilizce kelime ve Eğer zorunda gidiyoruz
akıllıca bunları yüklemek için nasıl anlamaya belleğe, RAM'e, bazı verileri kullanarak
Seçtiğiniz yapısı.
>> Şimdi böyle bir veri yapısı olabilir olmamalıdır muhtemelen, fakat
Oldukça basit bağlantılı liste, hangi biz son kez tanıttı.
Ve bir bağlantılı liste, en azından vardı Bir dizi üzerinde bir avantaj.
Bir avantajı neler var belki bir bağlantılı liste?
>> İZLEYİCİ: Ekleme.
>> DAVID MALAN: Ekleme.
Bununla ne demek istiyorsun?
>> İZLEYİCİ: Anywhere birlikte Liste [duyulamaz].
>> DAVID MALAN: İyi.
Yani bir eleman yerde ekleyebilirsiniz Listenin ortasında istiyorum
bir şey karıştırmak zorunda kalmadan, hangi bizim sıralama içinde, sonucuna
tartışmalar, değil mutlaka iyi bir şey,
o zaman alır, çünkü aslında taşımak için Bu insanların hepsi sola veya sağa.
Ve böylece bir bağlantılı liste ile yapabilirsiniz Sadece malloc ile tahsis, yeni bir düğüm,
ve daha sonra birkaç güncelleme pointers-- iki, üç operasyon max--
ve biz birini yuvası edebiliyoruz Bir liste halinde her yerde de.
Başka >> Ne avantajlı oldu Bağlantılı bir listesiyle ilgili?
Evet?
>> İZLEYİCİ: [Duyulmaz]
DAVID MALAN: Mükemmel.
Mükemmel.
Gerçekten dinamik var.
Ve işlemekten değil ki, peşin, bazı sabit boyutu
bellek yığın, gibi olurdu Bir dizi ile, yukarı doğru olan
Eğer yalnızca düğümleri tahsis olmasıdır talep ve böylece sadece kadar alanı kullanarak
Aslında ihtiyacınız olan.
Bir dizi aksine, sen olabilir yanlışlıkla çok az ayrılamadı.
Ve o zaman sadece gidiyor boyun bir ağrı olması
Yeni büyük dizi tahsis etmek, kopyalamak Her şey üzerinde, eski dizi ücretsiz
ve daha sonra işiniz hareket.
Ya da daha kötüsü, sen yol tahsis olabilir aslında ihtiyacınız olandan daha fazla bellek,
ve böylece bir çok için gidiyoruz tabiri caizse, dizi seyrek nüfuslu.
>> Yani bir bağlantılı liste bu size verir dinamizm ve esneklik avantajları
eklemeler ve silmeler ile.
Ama kesinlikle ödenen bir bedel var olmalıdır.
Temalar Aslında, bir sınav sıfır keşfedilmeyi
oldu dengeler bir çift Biz bugüne kadar gördük.
Yani a ödenen fiyat ya da ne var Bağlantılı bir liste olumsuz?
Evet.
>> İZLEYİCİ: Hayır rasgele erişim.
>> DAVID MALAN: Hayır rasgele erişim.
Ama kimin umurunda?
Rastgele erişim zorlayıcı gelmiyor.
>> İZLEYİCİ: [Duyulmaz]
DAVID MALAN: Kesinlikle.
Eğer sahip olmak istiyorsanız, Belirli bir algorithm--
ve ben aslında teklif izin Özellikle ikili arama, hangi
biz oldukça Kişilik Sokak kullandım biridir Eğer rasgele erişim yoksa,
Eğer bu basit aritmetik yapamaz Orta eleman bulma gibi
ve sağ atlama.
Bunun yerine ilk başta başlamak zorunda eleman ve doğrusal soldan arama
sağa bulmak istiyorsanız orta veya diğer herhangi bir unsuru.
>> İZLEYİCİ: Muhtemelen daha fazla bellek alır.
>> DAVID MALAN: daha fazla bellek Alır.
Nerede ek bir bellekte gelen maliyet?
>> İZLEYİCİ: [Duyulmaz]
DAVID MALAN: Kesinlikle.
Burada bu durumda, biz tamsayılar için bir bağlantılı liste,
ve henüz biz iki katına ediyoruz bellek miktarı
biz de bu işaretçileri saklayarak gerekir.
Gibi büyük bir anlaşma Şimdi daha az senin yapılar büyük olsun
ve bir numara depolamak ama belki bir öğrenci ya da başka bir nesne.
Ama nokta kesinlikle kalır.
Ve böylece operasyonların bir dizi bağlantılı listelerde çağrıldı
n- doğrusal büyük O idi.
Ekleme veya arama gibi şeyler veya davanın bir eleman olarak silme
en sonunda olması oldu bu sıralama dışı olup olmadığı listesi.
>> Bazen şanslı olsun ve olabilir Bu operasyonlar öylesine alt sınır
sen eğer aynı zamanda sabit zaman olabilir her zaman ilk elemanı bakarak,
örneğin.
Ama sonuçta, biz söz Holy Grail ulaşmak için
Veri yapıları ya da Bazı yaklaşım bunların,
zaman sabiti, bu arada.
Biz öğeleri bulmak veya öğeleri ekleyebilir miyim veya bir listeden öğeleri kaldırmak?
Biz çok yakında göreceğiz.
Ve o bir dışarı çıkıyor Biz konum mekanizmaların
Bugün kullanmaya başlayacak, p yıllık kullanım, beş set
aslında oldukça tanıdık.
Örneğin, bu bir demet halinde sınav kitapların, her biri
Bir öğrencinin ilk sahiptir Üzerinde son ismi,
ve ben onları pick up Bir sınav sonunda,
ve hepsi güzelsin rastgele bir sırayla çok,
ve biz sıralama hakkında gitmek istiyorum Bu sınavlar böylece bir kez derecelendirildi
sadece çok daha kolay ve hızlı onları geri el
alfabetik öğrencilere.
Içgüdülerin ne olurdu Bu gibi sınavlardan bir yığın için?
>> Peki, siz de benim gibi iseniz, Bu m olduğunu görebilirsiniz,
bu yüzden, çeşit içine bu koymak için gidiyorum Bu benim tablo veya benim zemin ise
Ben bir şeyler yayılıyor ediyorum Şunları bir konrtol ya da benim dizi gerçekten--
Ben orada Ms tüm koymak olabilir.
Ah.
İşte bir A. yüzden belki var Burada As koydu.
Ah.
İşte ben gidiyorum başka A. var buraya koymak için.
İşte Z. İşte başka M. Ve böyledir Ben böyle yığınları yapmaya başlamak olabilir.
Ve sonra belki daha sonra gitmek istiyorum ve çeşit çok nitpicky-ly sıralama
Bireysel kazıklar.
Ama gelin ben bakmak ederim Ben teslim olduğum girişindeki
ve bazı hesaplanır yapacak O girişine göre karar.
O A ile başlıyorsa, oraya koydum.
O Z ile başlıyorsa, bunu üzerine koymak arasında var, ve her şeyi.
>> Yani bu var bir tekniktir Genellikle hashing-- lH-A-S-H- olarak bilinen
hangi genelde almak demektir giriş ve hesaplamak için bu girişi kullanarak
değeri, genel olarak çok sayıda, ve numara depolama içine indeks
konteyner, bir dizi gibi.
Bu yüzden, diğer bir deyişle, bir olabilir hash fonksiyonu, kafamda gibi,
Birisi bu görürsem o A ile başlayan isim,
Ben o haritaya gidiyorum kafamda sıfıra.
Ben Z birini görürsen, ben değilim Kafamın içinde 25 bu haritaya gidiyor
ve sonra içine koymak son, en kazık.
>> Şimdi, eğer beynim değil düşünmek ama bir C programı, ne numaralar olabilir
Eğer aynı sonucu elde etmek güveniyor?
Diğer bir deyişle, eğer ASCII karakter A vardı
nasıl belirliyorsunuz ne kepçe koymak için?
Muhtemelen istemiyorum kova 65, içine koymak
Orada gibi olurdu iyi bir neden için.
Nereye A koymak istiyorum ASCII değeri açısından?
Nereye onun ASCII yapmak istiyorsun değer bir akıllı kova ile gelip
koymak için?
>> İZLEYİCİ: Eksi A.
>> DAVID MALAN: Evet.
Yani eksi A veya eksi özellikle 65 o ise
sermaye A. Veya 98 ise Bir küçük bir var.
Ve böylece çok bize sağlayacak basit ve çok aritmetik,
Böyle bir kovaya bir şey koymak.
Yani biz aslında yapmak çıkıyor Bu aynı zamanda, hatta sınavlar ile.
Hatırlayacağınız olabilir Yani >> Eğer çember senin kapaktaki öğretim arkadaşın adı.
Ve TF isimleri düzenlendi alfabetik bu sütunlara,
iyi, ister inanın ister inanmayın, zaman hepimiz 80 artı
, sınıfa geçen gece birlikte var Bizim derecelendirme sürecinde son adım
Büyük bir içine sınavlar karma için [duyulamaz] zemine uzay
ve herkesin sınavlar düzenlemek için kendi TF yılların tam sırayla
kapaktaki isimler, çünkü o zaman bizim için çok daha kolay
Bu kullanarak doğrusal arama için arama veya zeka çeşit
TF bulmak için onun veya Onun Öğrencilerin sınavlar.
Karma bir >> Yani bu fikir sen görürsünüz
Oldukça güçlü aslında güzel sıradan ve çok sezgisel,
çok belki bölmek gibi ve fethet haftada sıfır oldu.
Hackathon ben hızlı ileri Birkaç yıl önce.
Bu Zamyla ve bir çift oldu diğer personel tebrik öğrencileri
onlar geldi.
Ve biz katlama bir sürü vardı isim etiketleri ile orada tablolar.
Ve biz isim etiketleri düzenledi Orada üzerinde As gibi
ve orada Zs.
Ve böylece TFs biri çok akıllıca Talimatlar olarak bu yazdı
gün.
Ve dönem bu hafta 12 tüm mükemmel mantıklı ve herkes yaptı
ne yapacağını biliyordu.
Ama her zaman size ettik Aynı şekilde sıraya,
Eğer uygulama konum Bir karma aynı kavramı.
Yani bu biraz resmileştirmek verelim.
İşte bir dizidir.
Biraz olmak üzere çizilmiş Geniş sadece görsel, tasvir,
Biz dizeleri koymak olabilir Böyle bir şey.
Ve bu dizi açıkça boyutu 26 toplam.
Ve bir şey denir masa keyfi.
Ama bu sadece bir sanatçının yorumuyla olduğu Bir karma tablo ne olabileceğini.
>> Yani bir karma tablo şimdi gidiyor Bir üst düzey veri yapısı.
Günün sonunda Size görmek üzereyiz
Bir karma tablo, uygulamaya hangi çok check-in hattı gibi
çok böyle bir hackathon de masa sınav kitapları sıralamak için kullanılır.
Ama karma tablo Bu yüksek seviyede sıralama
Bir dizi kullanabilirsiniz kavramı , davlumbaz bunu uygulamak için altında
ya da bir uzunluk listesini kullanmak, hatta olabilir belki bazı diğer veri yapıları.
Ve şimdi bu theme-- alma var Bu temel bileşenlerin bazıları
Bir dizi ve bu bina gibi uzunluğu listesinin hemen bloke
ve biz inşa edebilirsiniz başka ne görmeye Bunların üstüne, maddeler gibi
Bir tarifi içine, daha yapım ilginç ve kullanışlı nihai sonuçlar.
>> Karma tablo ile Böylece Biz bunu uygulamak olabilir
bellekte resimsel bu gibi ama nasıl aslında yukarı kodlanmış olabilir?
Peki, belki de basitçe budur.
Tüm kapaklar KAPASİTE, sadece ise Örneğin 26 için bir constant--,
alphabet-- 26 harfler için Benim değişken tablo diyebilirsiniz,
ve ben gidiyorum iddia olabilir Orada, ya da dize karakter yıldız koymak.
Yani o kadar basit olmadığını, bu gibi Bir hash tablosu uygulamak istiyorum.
Ve yine, bu gerçekten sadece bir dizidir.
Fakat yine de, bir karma tablo ne olacak şimdi
Sadece bu soyut bir veri türü çağrı üstüne bir kavramsal tabakaların tür
daha dünyevi bir şey Şimdi bir dizi gibi.
>> Şimdi, nasıl gidiyoruz yapmak sorunlarının çözümü hakkında?
Peki, daha önce ben lüks vardı burada yeterli tablo alanı olan
Ben koymak böylece sınavlar yerde ben istedim.
Yani şöyle burada gidebilir.
Zs buraya gidebilir.
Ms buraya gidebilir.
Ve sonra bazı ekstra boşluk vardı.
Ama bu bir hile hakkının bir parçasıdır Şimdi bu tabloda, çünkü ben eğer gerçekten
bir dizi olarak bunu düşündüm, sadece bir Bazı sabit boyutta olacak.
>> Yani teknik olarak, ben çekerseniz Başka bir öğrencinin sınav kadar
ve bu kişinin, oh, bakın isim, çok bir A ile başlar
Ben tür oraya koymak istiyorum.
Ama en kısa sürede ben eğer, orada dediği gibi Bu tabloyu gerçekten bir dizi temsil,
Ben geçersiz kılma veya clobbering için gidiyorum kim bu öğrencinin sınav olduğunu.
Doğru?
Bu bir dizi ise, tek bir şey olabilir Bu hücrelerin ya da elemanların her gidin.
Ve bu yüzden bir tür var almak ve seçin.
>> Şimdi önce ben tür hile ve bu veya ben yaptım
sadece tür yığılmış Her diğerinin üzerinde onları.
Ama bu kodda uçmak için gitmiyor.
Yani nerede koyabilirsiniz Adını, ikinci öğrenci
Ben vardı bu ise A Mevcut tablo alanı?
Ve ben üç yuva ve kullandım Sadece bir kaç diğerleri var gibi görünüyor.
Ne yapabilirdi?
HEDEF KİTLE: [Duyulmaz]
DAVID MALAN: Evet.
Belki Sadece basit tutalım.
Doğru?
Ben koymak istiyorum nerede uymuyor.
Yani koymak için gidiyorum teknik bir B gitmek istiyorum nereye.
Şimdi, tabii, ben başlıyorum Bir köşeye kendimi boyamak için.
Ben bir öğrenci alırsanız Adını aslında B,
Şimdi B biraz hareket olacak ileri, gibi, evet, ne olabilir
Bu bir B ise, şimdi buraya gitmek zorunda.
>> Ve böylece bu çok hızlı bir şekilde , sorunlu hale gelebilir
ama bir teknik, bu aslında doğrusal tarama olarak adlandırılır,
bu sayede sadece düşünün sizin Dizi hattı boyunca olmak.
Ve sen sadece tür soruşturma veya Her mevcut elemanı kontrol
kullanılabilir bir yer arayan.
Ve en kısa sürede bulmak gibi bir, sen orada bırakın.
>> Şimdi, fiyat şimdi ödenmekte Bu çözüm için ne olduğunu?
Biz sabit bir boyut dizi var, ve ben isimleri eklediğinizde
içine, en azından başlangıçta, ne sokma çalışma süresi
öğrencilerin 'koymak için Doğru kovalarda sınavlar?
Neyin Büyük O?
>> İZLEYİCİ: n.
DAVID MALAN: Ben n büyük O duydum.
Doğru değil.
Ama biz ayrı alay edeceğiz neden sadece bir an.
Başka ne olabilir?
>> İZLEYİCİ: [Duyulmaz]
DAVID MALAN: Ve bana görsel yapalım.
Yani bu mektup S. olduğunu varsayalım
>> İZLEYİCİ: Bu biri.
DAVID MALAN: Bu biri.
Doğru?
Bu dizi, olduğu rastgele erişim anlamına gelir.
Ve biz bu düşünüyorsanız sıfır ve bu gibi 25 olarak,
ve biz farkında, oh, burada benim girişi S var,
Ben kesinlikle dönüştürebilirsiniz S ASCII karakter,
karşılık gelen bir sayıya sıfır ile 25 arasında
ve hemen ait olduğu yere koymak.
>> Ama tabii, en kısa sürede ben almak gibi isim, ikinci bir kişi A veya B veya C
Sonunda, ben kullandım, eğer lineer, benim çözüm olarak sondalama
çalışma süresi En kötü durumda ekleme
aslında ne içine intikal edecek?
Ve ben burada duydunuz doğru erken.
HEDEF KİTLE: [Duyulmaz]
DAVID MALAN: Yani gerçekten bir kez n Eğer yeterince büyük bir veri seti var.
Böylece, bir yandan, eğer senin dizi yeterince büyük
ve verileriniz size yeterince seyrek Bu güzel sabit zaman olsun.
Ama en kısa sürede başlatmak gibi Daha fazla ve daha fazla eleman alma,
ve sadece istatistiksel olsun harfi ile daha fazla kişi
Bir şekilde kendi adını veya mektup B, potansiyel olabilir
bir şey daha doğrusal dönüşebilir.
Yani oldukça mükemmel değil.
Yani biz daha iyi yapabileceğini?
>> Peki, ne oldu bizim çözüm ne zaman biz önce
daha fazla dinamizm istiyorum Bir dizi gibi bir şey izin?
HEDEF KİTLE: [Duyulmaz]
DAVID MALAN: Ne tanıtmak mı?
Evet.
Yani bir bağlantılı liste.
Peki, bir bağlantılı ne görelim Liste yerine bizim için yapabilir.
Peki, beni bu biz teklif edelim aşağıdaki gibi resim çizmek.
Şimdi bu farklı Örneğin gelen görüntü
Farklı bir metin, aslında, o aslında boyutu 31 bir dizi kullanıyor.
Ve bu yazar sadece dizeleri hash karar
kişinin adlarına göre değil, ama onların doğum tarihleri ​​esas.
Bağımsız olarak ayın, bu biçim Bir ayın ilk doğan eğer
veya ayın 31., yazar Bu değere göre karma olacak,
biraz dışarı isimleri yaymak amacıyla sadece 26 noktalar izin verebilir daha fazla.
Ve belki de biraz daha üniforma var alfabetik harflerle giderek daha,
Çünkü elbette muhtemelen orada isimler ile dünyanın daha fazla kişi
Kesinlikle daha bir o başlangıç alfabenin diğer bazı harfler.
Yani belki bu biraz daha homojen, varsayarak
düzgün bir dağılım Bir ay boyunca bebeklerin.
>> Ama, tabii, bu hala eksik olduğunu.
Doğru?
Biz çarpışmalar yapıyoruz.
Bu Çoklu insanlar veri yapısı halen
en azından aynı doğum sahip Eğer ayın bakılmaksızın konum.
Ama yazar ne yapmış?
Biz bir dizi var gibi Eh, o görünüyor dikey çizilmiş sol tarafta,
ama bu sadece bir sanatçının sunumu var.
It does not matter ne yönde size Bir dizi çizmek, yine bir dizi var.
Bu görünüşte bir dizi nedir?
>> İZLEYİCİ: Bağlantılı listesi.
>> DAVID MALAN: Evet.
Bir var gibi görünüyor bağlantılı liste dizisi.
Yani yine, tür bu noktaya Şimdi bu veri yapılarını kullanarak
daha fazla madde olarak ilginç çözeltiler,
kesinlikle bir alabilir Temel, bir dizi gibi,
ve daha sonra bir şey almak Bağlantılı bir listesi gibi ilginç
ve hatta daha da içine bunları birleştirmek daha ilginç veri yapısı.
Ve gerçekten de, bu çok olur Bir karma tablo denir,
böylece dizi Gerçekten hash tablosu,
ama bu karma tablo var zincirler, bu yüzden, konuşmak
Bu büyüyebilir veya dayalı küçültmek elemanlarının sayısı Eklemek istediğiniz.
>> Şimdi buna göre, ne Şimdi çalışma süresi?
Birini eklemek istiyorsanız 31 Ekim kimin doğum günü,
Nerede o gidiyor?
Tamam.
O 31 diyor çok altında.
Ve bu mükemmel.
O zaman sabiti oldu.
Ama biz başka birini ne bulursanız kimin doğum günü, bakalım edilir,
Ekim, Kasım, Aralık 31?
Nerede o gidecek?
Aynı şey.
Olsa İki adım.
Yani olsa sabit değil mi?
Tamam.
Şu anda öyle.
Ancak genel durumda, Biz eklemek daha fazla insan,
olasılıksal, biz gidiyoruz daha çarpışmalar alır.
>> Şimdi bu biraz iyi teknik Çünkü
Şimdi benim zincirler olabilir En kötü durumda ne kadar?
Ben bunu daha içine n insanları eklerseniz gelişmiş veri yapısı, n insanlar,
En kötü durumda o n olacak.
Neden?
>> İZLEYİCİ: Çünkü eğer herkes Aynı doğum günü var,
onlar tek satır olması için gidiyoruz.
DAVID MALAN: Mükemmel.
Bu, biraz yapmacık olabilir ama gerçekten kötü durumda,
herkes aynı doğum günü varsa, Eğer sahip girdiler verilen,
Eğer bir için gidiyoruz kitlesel uzun zincirli.
Ve böylece, bunu bir çağrı olabilir tablo hash, ama gerçekten var
sadece büyük bir bağlantılı liste israf alanı bir sürü.
Ama genel olarak, biz varsayalım eğer en az doğum uniform-- olan
ve muhtemelen değildir.
Ben o kadar yapıyorum.
Ama biz varsayalım eğer, için tartışma hatır
Onlar, daha sonra teorik olarak, eğer olduklarını bu dikey temsilidir
dizinin, iyi o zaman umarım sen vardır, bilirsin zincirleri almak için gidiyoruz,
hemen hemen aynı uzunlukta burada her bir Bu ayın bir gününü temsil eder.
>> Ayda 31 gün var Şimdi eğer, O gerçekten benim çalışma süresi anlamına gelir
31 üzerinde n büyük O, olduğu Doğrusal daha iyi hissediyor.
Ama biri ne bizim taahhütler birkaç hafta
önce bu ifade için geldi zaman Bir algoritmanın çalışma süresi?
Sadece sadece yüksek mertebeden dönem bakmak.
Doğru?
31 kesinlikle yararlıdır.
Ama bu yine de n büyük O'dur.
Ama temalardan birini sorunu beş set
için olacak Kesinlikle kabul,
asimptotik, teorik Bu veri yapısı
Sadece daha iyidir bir büyük bağlantılı liste.
Ve gerçekten de, en kötü durumda, bu karma tablo bu içine intikal olabilir.
>> Ama gerçek dünyada, bize insanlar Kendi Mac veya PC veya ne olursa olsun
ve gerçek dünya çalıştıran gerçek dünya verileri yazılım,
hangi algoritmanın tercih edeceksin?
son adımlar ya götüren bir n 31 adımda bölünmesiyle alır bir
bazı veri parçası bulmak için veya bazı bilgileri aramak için?
Ben kesinlikle 31 yapar demek Gerçek dünyada bir fark.
Bu 31 kat daha hızlıdır.
Ve biz insanlar kesinlikle vardır takdir gidiyor.
>> Yani ikilemi fark Orada aslında arası
teorik şeyler hakkında konuşmaya Kesinlikle ve asimtotik hangi
Gördüğümüz gibi bir değere sahiptir, ama gerçek dünyada,
Sadece yapma hakkında bakım Genel girişler için insan mutlu,
Eğer çok iyi kabul etmek isteyebilirsiniz Evet ise, bu doğrusal, aslında,
ancak 31 kat daha hızlı olduğunu daha doğrusal olabilir.
Ve daha iyisi, biz sadece gerekmez Bir doğum tarihi gibi keyfi bir şey yapmak,
biz biraz harcayabilirsiniz daha fazla zaman ve akıllılık
ve biz ne yapacağını düşünmek, Verilen bir kişinin ismi ve belki
kendi doğum olanlar birleştirmek için maddeler şey anlamaya
Bu gerçekten daha üniforma ve az çentikli,
bu nedenle bu resim daha konuşmak Şu anda bu olabilir göstermektedir.
Nasıl kodu bu uygulamak?
Peki, beni bu biz teklif edelim sadece biz ettik bazı sözdizimi ödünç
Bugüne kadar bir kaç kez kullanılır.
Ve ben tanımlamak için gidiyorum Bir düğüm, bu durum, yine
sadece bazı için genel bir terimdir bir veri yapısı için kap.
Bunu teklif edeceğim bir dize orada oluyor.
Ama biz çekmeye başlamak için gidiyoruz Şimdi kapalı tekerlekleri eğitim bu.
>> Daha fazla CS50 kütüphanesi Gerçekten, istediğiniz sürece
senin finali için kullanmak ince proje,
ama şimdi biz geri çekmek için gidiyoruz perde ve sadece bir karakter yıldızı olduğunu söylüyorlar.
Kelime Yani orada olacak Söz konusu kişinin adı.
Ve şimdi ben bir bağlantı var Burada bir sonraki düğüme
Bu temsil etmesi için, düğümlerin her biri
zincir içinde, potansiyel olarak, Bağlantılı bir liste.
>> Ve şimdi nasıl beyan yapmak karma tablo kendisi?
Nasıl bütün bu yapıyı beyan edersiniz?
Peki, gerçekten, çok ben bir gösterici eskisi gibi Bir listenin sadece ilk elemanına
önce, benzer sadece söyleyebiliriz Ben sadece işaretçiler bir demet gerekir
Bütün bu hash tablosu uygulamak için.
Ben bir dizi var gidiyorum karma tablo için çağrıda tablo.
Bu boyut kapasitesinin olacak.
Yani o sığabilecek kaç unsurlar var.
Ve bu unsurların her biri Dizi düğüm yıldızı olacak.
Neden?
Peki, bu resim başına, ben ne olduğumu karma tablo olarak uygulanması
etkin bir de başlangıcı sadece bir Biz dikey boğuldum bu dizi,
olan kareler her Bir işaretçi temsil eder.
Olanlar bu eğik çizgi var ki Bunların içinden sadece null.
Ve olanlar bu var sağa gidiyor oklar
Gerçek düğümler gerçek işaretçiler, Bir bağlantılı liste başlangıcını ergo.
>> Yani burada, daha sonra, nasıl olabilir olduğunu bir karma tablo uygulamak
Ayrı zincirleme uygular.
Şimdi daha iyi yapabiliriz?
Pekala ben son kez söz ki Biz sürekli zaman elde edebiliriz.
Ve ben tür size verdi Burada zaman sabiti,
ama sonra gerçekten dedi zaman sabiti hala çünkü
toplam bağımlı elemanların sayısı
Eğer içine giren konum veri yapısı.
Ama biz bu yaptığımız varsayalım.
Beni buraya ekrana geri dönelim.
Beni de burada bu kadar proje net Let Ekran ve ben bunu herhalde.
Adını eklemek istedim varsayalım Daven benim veri yapısı içine.
>> Yani bir dize eklemek istiyorum Veri yapısı içine DAV.
Ne bir kullanmak istemiyorsanız tablo hash, ama ben kullanmak
Dahası şey ağaç gibi Bir aile ağacı gibi
Eğer bazı kök var Üst ve sonra düğümleri ve yaprakları
Bu aşağı ve dışa doğru gidin.
, O ben varsayalım Daven en eklemek istiyorum
Şu anda boş bir liste ne içine.
Ben aşağıdaki yapmak için gidiyorum: Ben Bu ailede bir düğüm oluşturmak için gidiyor
ağaç gibi veri yapısı görünüyor Biraz böyle, her biri
dikdörtgenler, diyelim etti içinde hemen 26 elemanları.
Ve hücrelerin her Bu dizide gidiyor
Bir alfabenin mektubu temsil etmek.
>> Özellikle, tedavi için gidiyorum bu, A, daha sonra B, sonra C, sonra D
Burada bu.
Yani bu etkili oluyor yazmak D. temsil
Ama Daven en tüm eklemek için Ben biraz daha yapmamız gerekiyor isim.
Bu yüzden ilk tabiri caizse, karma gidiyorum.
Ben ilk harfi bakmak için gidiyorum içinde Daven en Açıkçası D olan,
ve ben ayırmaya gidiyorum görünen bir düğüm
gibi büyük bir büyük bir dikdörtgen bu-- Tüm alfabeyi sığacak kadar.
>> Şimdi Ge yapılır.
Şimdi A. D-A-V-E-N hedeftir.
Yani şimdi ben yapacağım bu ne.
En kısa sürede D bildirimi başladı Orada hiçbir işaretçi yok.
Bu, şu anda çöp değerleri var ya da ben null başlatılamıyor olabilir.
Ama ben ile devam edelim Bir ağaç bina bu fikir.
Bana bu başka birini tahsis edelim İçinde 26 elemana sahiptir düğümleri.
>> Ve biliyor musun?
Bu bellekte sadece bir düğüm ise bu Bir yapı kullanılarak malloc'dan ile oluşturulan
yakında göreceğimiz gibi, Ben bu-- yapacağım
Ben bir ok çizmek için gidiyorum Aşağı D temsil şey
Bu yeni düğümün.
Ve ilk sonraki şimdi Daven adına mektup,
V-- D-A-V-- ben önde gitmek için gidiyorum ve bu gibi başka bir düğüm çizmek,
bu sayede, burada V elemanı, Biz instance-- hoppala için çekersiniz.
Biz orada çizmek olmaz.
Burada gidecek.
>> Sonra biz gidiyoruz Bu V. olarak düşünün
Ve sonra buraya biz indeksi gidiyoruz aşağı V biz E. düşünün ne yapacaksınız içine
Ve sonra buradan biz gidiyoruz Burada bu düğümlerin birine sahip gidin.
Ve şimdi cevaplamak için bir sorum var.
Bunu belirtmek bir şekilde gerek Biz dize Daven sonunda konum.
Yani sadece boş bırakabilir.
>> Ama biz Daven en ne varsa Ayrıca tam adı, hangi
biz Davenport söylediğim gibi, değil mi?
Böylece DAV ne ise Aslında bir alt,
çok daha uzun bir dize bir önek?
Biz sadece kalıcı olamaz hiçbir şey gidiyor demek
Çünkü biz olabilir, oraya gitmek için Davenport gibi bir kelime eklemek asla
Bu veri yapısı içine
>> Peki neler yapabileceğini yerine ise Bu unsurların her biri tedavi
belki iki sahip bunların içinde elemanları.
Bir, gerçekten, bir gösterici ben yapıyorum.
Bu kutuların her Yani Sadece bir hücre.
Ama ne olursa üst Şehre alt kişinin
Çünkü, boş olacak henüz hiçbir Davenport yoktur.
Ne olursa üst bir Bazı özel değer?
Ve biraz olacak Bu boyutta çizmek zor.
Ama bu sadece bir onay işareti olduğunu varsayalım.
Kontrol edin.
D-A-V-E-N dizedir Bu veri yapısı içinde.
>> Bu arada, ben olsaydı daha fazla alan Burada, ben, P-O-R-T yapabileceği
ve ben düğüm onay koyabilirsiniz Bu çok sonunda harfi T sahiptir.
Yani bu bir kitlesel bir Karmaşık görünümlü veri yapısı.
Ve benim el yazısı kesinlikle yardımcı olmuyor.
Ama bir şey eklemek istedim Başka, biz ne yapacağını düşünün.
Biz David koymak istedim, biz aynı mantığı, D-A-V takip ediyorum
ama şimdi bir sonraki işaret ediyorum eleman değil E, ancak I'den D.
Yani orada oluyor Bu ağacın daha fazla düğüm.
Biz daha fazla arama malloc zorunda gidiyoruz.
Ama ben yapmak istemiyorum Bu resmin tam bir karışıklık.
Yani bunun yerine bir bakalım Bu-ön formüle oldu
nokta değil bu böyle, nokta, noktalar, ama sadece kısaltılmış diziler.
Ama düğümlerin her Burada bu ağaç up
Aynı şey-- temsil Bir dizi boyutu 26 Ray.
>> Ya biz olmak istiyorsanız Gerçekten doğru şimdi, ne
Birinin adı olarak eğer bir kesme işareti, diyelim
Her düğüm aslında olduğunu varsayalım İçinde 27 endeksleri, sadece 26 gibi.
Yani bu artık bir veri olacak yapı trie-- T R-l-E olarak adlandırılan.
Sözde bir tray, Bir ağaç için tarihsel bir akıllı isim
Bunun için optimize alımı, hangi elbette,
bu tray yüzden I-E ile yazıldığından.
Ama bu trayın tarihidir.
>> Yani tray bu ağaç gibi veri Bir aile ağacı gibi yapı
sonuçta böyle davranır.
Ve burada bir sadece başka bir örnek diğer insanların isimleri sürü.
Ama şimdi soru eldeki ne var
Biz belki bir daha getirerek kazandı karmaşık veri yapısı, ve bir,
açıkçası, bu çok fazla bellek kullanır.
>> Halde olduğundan, Şu anda, ben sadece kulüpler
D'nin işaretçi kullanarak ve A V ve Es ve Ns, ve
Ben bellek çok bir halt israf ediyorum.
Ama bir kaynak harcamak nerede, Ben geri başka kazanmak yapmak eğilimindedir.
Ben daha fazla yer harcıyorum Yani eğer Muhtemelen umut ne?
Ben ne az harcama ediyorum?
HEDEF KİTLE: Az zaman.
DAVID MALAN: Zaman.
Şimdi neden olabilir?
Peki, ekleme nedir Zaman, hemen büyük O açısından,
Daven gibi bir isim veya Davenport veya David?
Peki, Daven beş adım oldu.
Davenport dokuz adımlar olacaktır, bu yüzden bir kaç adım daha olacaktır.
David de beş adım olacaktır.
Yani bu somut sayılar, ama kesinlikle var
bir üst sınır Birinin adının uzunluğu.
Ve gerçekten de, sorun Beş şartname setleri,
Önerdiğimiz gidiyoruz bir şey olduğunu
Bu 40-bazı küsur karakterler var.
>> Gerçekçi, kimse sahip sonsuz uzun isim,
demek olan bir uzunluğu isim veya bir dize uzunluğu biz olabilir
Devlet belirli var yapı tartışmasız ne olduğunu?
Bu sabit değil.
Doğru?
Bu gibi büyük bir sabit olabilir 40-bir şey, ama sabittir.
Ve kaç hiçbir bağımlılık vardır Diğer isimler bu veri yapısı vardır.
Diğer bir deyişle, eğer ben Şimdi eklemek istedim
Colton veya Gabriel ya da Rob ya Zamyla veya Alison ve Belinda ya da başka bir isim
Bu veri içine personelinden yapısı, çalışma süresi olan
diğer isimleri ekleyerek Etkilenen tüm en olacak
kaç diğer elemanları tarafından olan Zaten veri yapısı içinde?
Öyle değil.
Doğru?
Biz etkili kullanarak Çünkü Bu çok katmanlı karma tablo.
Ve çalışma süresi Bu işlemlerin herhangi birini
sayısına bağımlı değildir veri yapısı içinde olan unsurlar
veya sonunda gidiyor veri yapısı içinde olması,
ama ne özellikle uzunluğuna?
>> Dize olmak , takılı yapmak yok ki
Bu asimptotik sabit birinin seferinde-- büyük Ç.
Ve açıkçası, sadece Gerçek dünya, bu
Daven adı alır takmadan demektir Beş adımda, ya da Davenport dokuz gibi
adımlar, ya da David beş adım.
Bu oldukça lanetlemek küçük çalışma süreleri var.
Ve, gerçekten de, bu çok var iyi bir şey, özellikle
toplamda bağımlı değil Orada elemanların sayısı.
Bu yüzden bu uygulamaya nasıl kod yapısının tür?
Biraz daha var Karmaşık, ama yine de var
sadece bir uygulama temel yapı taşları.
Ben yeniden tanımlamak için gidiyorum Bize düğüm şöyle:
bool word-- denir ve bu bir şey denilebilir.
Ama bool temsil ne bir onay işareti olarak çekti.
Evet.
Bu dize sonu Bu veri yapısı içinde.
>> Ve, elbette, düğüm yıldızı çocuklara orada atıfta olduğunu.
Ve, gerçekten de, tıpkı Bir aile ağacı, sen
düğümleri düşünün Bu asılı olan
Bazı ebeveyn alt eleman çocukları olmak.
Ve böylece çocuklar gidiyor 27 dizisi, 27 biri
Sadece kesme işareti için olmak.
Biz sıralamak için gidiyoruz özel bir durum bunun.
Yani belli olabilir kesme ile isimleri.
Belki de tire gerektiği oraya, ama sen olacak
p seti 5 sadece bakım görmek harfler ve kesme konusunda.
>> Ve sonra nasıl temsil ediyorlar veri yapısı kendisi?
Nasıl kök temsil ediyor Bu trayın, tabiri caizse?
Peki, sadece, bir bağlantılı liste ile mi İlk elemana bir işaretçi gerekir.
Bir tray ile sadece bir ihtiyaç Bu trayın köküne işaretçisi.
Ve oradan karma yapabilirsiniz yolunuzu aşağı derin ve daha derin
yapısında her düğümün.
Yani sadece bu can ile biz o yapı temsil eder.
>> Şimdi, Ah soru Meanwhile--.
>> İZLEYİCİ: bool kelime nedir?
>> DAVID MALAN: Bool kelime Sadece bu C enkarnasyon
Ben tarif ne Burada, bu kutuda
Ben her yarma başladı İki parçaya dizinin elemanları.
Bir sonraki düğüme bir göstericidir.
Diğer olmak zorunda Bir onay kutusu gibi bir şey
Bir var, evet demek için burada biter DAV kelime,
Biz istemiyoruz, çünkü Şu, Dave.
>> Dave olacak olsa meşru bir kelime, o traya içinde değil
Henüz.
Ve D bir kelime değildir.
Ve D-A bir kelime ya da bir isim değil.
Onay işareti Yani sadece size bir kez gösterir
Bu düğüm vurmak Karakter önceki yol
Eklediğiniz aslında bir dize.
Böylece tüm bool var Bizim için orada yapıyor.
>> Denemeden üzerinde herhangi bir başka soru?
Evet.
>> İZLEYİCİ: örtüşme nedir?
Ne bir Dave ve Daven varsa?
DAVID MALAN: Mükemmel.
Ne bir Dave ve Daven varsa?
Biz eklemek Yani, bir takma ad söylüyorlar alakaları Dave-- D-A-V-E?
Bu aslında süper basit.
Yani biz sadece dört adımlar atmaya gidiyoruz.
D-A-V-E. Ve ben ne var Ben dördüncü düğümü vurdu kez yapmak?
Sadece kontrol edecek.
Biz zaten gitmek için iyi bir konum.
Bitti.
Dört adım.
Asimptotik zaman sabiti.
Ve şimdi biz hem Dave belitmişsin ve Daven yapısında dizeleri vardır.
Yani bir sorun değil.
Ve nasıl varlığını fark Daven ve bunu yapmadı
daha fazla zaman ya da daha az zaman alır Zaman Dave ve tersi.
>> Peki şimdi başka ne yapabiliriz?
Biz önce bu metafor kullandım tepsiler şey temsil.
Ama bu çıkıyor bir tepsilerin yığını aslında
Başka bir soyut veri demonstratif daha yüksek bir seviyeye veri yapısı type--
sonunda gün sadece olduğunu Bir dizi ya da bir bağlantılı liste gibi
daha sıradan falan.
Ama daha ilginç kavramsal kavramı.
Bu gibi bir yığın, Mather burada tepsileri,
genel olarak adlandırılır Sadece bir yığın ki-.
>> Ve veri yapısı bu tip İki operations-- var
Eğer bir adlandırılan itme için var yığına bir şey ekleyerek,
Başka bir tepsi koyarak gibi yığının üstüne geri.
Sizi anlamına gelir Ve sonra, pop üstteki tepsi off almak.
Ama yığını olduğunu hakkında önemli ne Bu meraklı özelliği var.
Yemekhane personeli gibidir Bir sonraki yemek için tepsileri yeniden düzenleyerek,
ne olacak Öğrencilere hakkında doğru
Bu veri yapısı ile etkileşim?
HEDEF KİTLE: Onlar bir kapalı pop gidiyoruz.
DAVID MALAN: Onlar için gidiyoruz bir kapalı, umarım üst pop.
Aksi takdirde sadece tür aptal alt tüm yol gitmek.
Doğru?
veri yapısı gerçekten izin vermez En azından alt tepsiyi kapmak için
Kolayca.
Yani bu meraklı var Bir yığın özellik
son öğe olduğunu İlki üzerinden olacak.
Ve bilgisayar bilim adamları çağrı Bu ilk dışarı son LIFO--.
Ve aslında var ilginç uygulamalar.
Mutlaka bazı kadar belirgin değil diğerleri, ama bu, gerçekten yararlı olabilir
ve bu, gerçekten, uygulanabilir farklı şekillerde bir çift.
>> Yani biri ve aslında, let bana bu dalmak değil.
Onun yerine bu yapalım.
Neredeyse olduğunu bir bakalım Aynı fikir, ama biraz daha adil olduğunu.
Doğru?
Bu fan erkek biri iseniz veya Gerçekten Apple ürünlerini seven kızlar
ve 03:00 uyandım Bazı mağazada hizaya
en son iPhone almak için, Böyle sıraya olabilir.
>> Şimdi sıra çok kasıtlı olarak adlandırılır.
Var çünkü bir çizgi var Bunun için bazı adalet.
Doğru?
Eğer ettik eğer bu tür emdi olur Apple Store'da ilk var
ama etkili alttaki vardır Tepsi sonra Apple çalışanları için
son kişi kim pop Aslında çizgi var.
Yığınlar ve kuyruklar, olsa Yani işlevsel onlar same-- tür konum
Sadece bu koleksiyonu kaynak de bu
Orada var shrink-- büyümeye gidiyor ve buna, bu eşitlik yönü
gerçek dünyada en azından nerede işlemleri egzersiz
temelde farklıdır.
Bir kuyruk bir stack-- rather-- olduğu söylenir
İki operasyon: n kuyruk d kuyruğu.
Yoksa onları arayabilirsiniz şeyler herhangi bir sayı.
Ama sadece yakalamak istiyorum bir ekleme olduğu düşüncesi
ve bir sonuçta çıkartmaktır.
>> Şimdi kaputun altında, hem yığın ve bir kuyruk nasıl uygulanabilir?
Biz koduna gitmeyecek çünkü daha yüksek düzeyde
Fikir çeşit daha açıktır.
Yani, insanlar ne yapmalıyım?
Ben Apple ilk kişiyim ise Mağaza ve bu ön kapı,
Eğer ben burada durmak gidiyorum, biliyorum.
Ve bir sonraki kişinin Burada durmak olacak.
Peki ne veri yapısı kendisi kuyruğa ödünç?
>> İZLEYİCİ: Bir kuyruk.
DAVID MALAN: Peki, bir kuyruk.
Tabii.
Başka ne?
>> İZLEYİCİ: Bir bağlantılı liste.
>> David MALAN: Bağlantılı Eğer uygulamak listesi.
Ve bir bağlantılı liste daha sonra da güzel aksine uzun keyfi büyüyebilir
Bazı sabit sayıda olması için mağaza insanların.
Ama belki bir sabit numara yerlerde meşrudur.
Onlar sadece 20 gibi varsa Çünkü belki ilk gününde iPhone'lar
onlar sadece boyutu bir dizi gerekir 20 O kuyruğunu temsil hangi
Biz konuşurken başladığınızda ancak şimdi söylemek olduğunu Bu üst düzey sorunlar hakkında,
bunu uygulayabilirsiniz yollardan herhangi bir sayıda.
Ve muhtemelen sadece gidiş var uzay ve zaman içinde bir ticaret kapalı
ya da sadece kendi kod karmaşıklığı.
>> Bir yığın ne?
Peki, bir yığın, biz de gördük Sadece bu tepsiler olabilir.
Ve bu bir dizi uygulamaya başladı.
Fakat bazı noktada, bir dizi kullanırsanız ne tepsilere ne olacak
aşağı koymak için çalışıyoruz?
Tamam.
Sadece gidiyoruz çok yüksek gitmek mümkün.
Ve onlar konum Mather düşünüyorum Aslında bu açılış gömme.
Yani aslında, neredeyse var Mather kullanıyor gibi
sabit boyutlu bir dizi Sadece can çünkü
o açılışta çok tepsileri uygun insanların dizlerinin altına kadar duvar.
Ve böylece olabilir Bir dizi olduğu söyleniyor,
ama biz kesinlikle uygulamak daha genel bir bağlantılı liste ile.
>> Peki, ne başka bir veri yapısı hakkında?
Beni burada görsel diğeri yukarı çekin bakalım.
Nasıl burada bu biri hakkında böyle bir şey?
Neden değil olması yararlı olabilir bir tray, gibi bir şey fantezi hangi
Biz bu çok geniş düğümler vardı gördüm bunların her biri, bir dizi içinde mi?
Ama biz bir şey daha ne yaparsanız sadece, eski bir okul aile ağacı gibi,
kimin burada düğümler her Sadece bir numara depolamak.
Bunun yerine bir ad veya bir torunu Sadece böyle bir numara depolamak.
>> Peki, jargon biz kullanmak veri yapıları hem çalışır olduğunu
ve ağaçlar, bir tray, yine, burada Sadece kimin düğümleri diziler bir,
hala ne olabilir İlkokuldan kullanmak
Bir aile yaptığı zaman tree-- yaprakları ve kök
ağaç ve çocuklarının ebeveyn ve bunların kardeşleri.
Ve biz bir ağaç uygulayabilir, Örneğin, basitçe bu kadar.
Bir ağaç, o takdirde bir düğüm, biri olarak bir numarası vardır bu çevreler,
o olacak değil bir gösterici, ancak iki.
Ve en kısa sürede eklemek gibi İkinci işaretçi, sen
Aslında şimdi sıralama yapabilirsiniz İki boyutlu verilerin
bellekte yapılar.
Iki boyutlu gibi çok Dizi yapabilirsiniz
İki-boyutlu tür var Bağlantılı listeler ama olanlar
bir model takip nerede olursa döngüleri var.
Bu biriyle gerçekten bir ağaç var Burada ve daha sonra büyükbaba yol kadar
Bazı ebeveynler ve çocuklar ve torunları ve torunlarının torunları.
ve benzeri yer alır.
>> Ama çok bu konuda gerçekten temiz ne, Sadece kod biraz sizi kızdırmak için,
dan geri çağırma yineleme süre geri, böylece
Eğer kendisini çağıran bir fonksiyon yazın.
Bu güzel bir fırsat bir şey uygulamak için
yineleme gibi, çünkü bu düşünün.
>> Bu bir ağaçtır.
Ve ben nasıl küçük bir anal oldum Ben sokağa tamsayılar koydu.
Öyle ki özel bir var İkili arama ağacı aşkına--.
Şimdi ikili duydum Seni aramak, ancak can
Bu şeyin adından geriye çalışır?
I nasıl desen nedir Bu ağaca tamsayılar takılı?
Bu keyfi değil.
Bazı desen var.
Evet.
>> İZLEYİCİ: soldaki küçük olanlar.
>> DAVID MALAN: Evet.
Küçük olanlar solda.
Büyük olanlar sağda.
Böyle bir gerçek ifadesi olduğunu bir ebeveyn, sol çocuğun daha büyüktür
sağ çocuğun daha ama daha az.
Ve yalnız o bile olduğunu özyineli sözlü tanım
Bunu uygulayabilirsiniz çünkü Her düğümün aynı mantık
ve sadece dipleri dışarı, bir taban durumda eğer
olacak, ne zaman birini vurdu Yaprakları, bu yüzden, konuşmak
Bir izin daha hiçbir çocuk babasıdır yerde.
>> Şimdi nasıl numarayı 44 bulabilir?
Sen, hm kökünde başlayacak ve söyleyebilirim.
55 Bu yüzden gitmek istiyorsun 44 değil sağa veya sola gitmek Ben istiyorsun?
Peki, açıkçası sol gitmek istiyorum.
Ve böylece sadece telefon gibi İkili arama kitap örneği
daha genel olarak.
Ama biz bunu uygulamak ediyoruz Şimdi biraz daha dinamik
Bir dizi izin verebilir daha.
Ve aslında, bakmak isterseniz kodu, ilk bakışta emin olun.
Bu satırları bir sürü gibi görünüyor.
Ama güzel basit.
Eğer bir işlevi uygulamak istiyorsanız Amacı hayatında denilen arama
Bir değer aramak için gibi, n bir tamsayıdır,
ve bir işaretçi olarak kabul ediyoruz köklerin düğüme bir işaretçi,
yerine, bu ağacın hangi Eğer, her şeyi erişebilirsiniz
nasıl delikanlı fark Eğer mantık uygulayabilirsiniz.
Ağaç null ise, Açıkçası orada değil.
Sadece yanlış dönelim.
Doğru?
Bunu hiçbir el varsa, Orada hiçbir şey yok.
>> Başka n daha az ise Şimdi n ok n- ağaç ok,
Biz süper tanıttı hatırlamak kısaca Geçen gün,
ve bu sadece de başvuru anlamına gelir işaretçi ve n adlandırılan alana bakın.
Yani oraya gitmek ve anlamı n adlandırılan alana bakmak.
Yani n ise, size verilen konum değeri, az ağaçlar tamsayı değerden,
nereye gitmek istiyorsun?
Sola.
>> Yani özyinelemeyi dikkat edin.
Ben gerçek returning-- ediyorum.
Sahte değil.
Ben ne olursa olsun cevap dönen ediyorum kendime bir çağrı dan, geçen
gereksiz yine n, ama şimdi biraz farklı ne?
Nasıl küçük bir sorun yapıyorum?
Ben ikinci olarak geçirerek argüman, ağacın kök değil,
ancak bu durumda, sol alt.
Yani sol çocukta geçiyorum.
>> Bu arada, n daha büyük ise, Şu anda bakıyorum düğüm,
Ben sağ tarafını arayın.
Else, ağaç, boş değilse ve eleman sola değilse
ve sağa değil vaka harika nedir?
Biz aslında düğüm buldum Soru ve bu yüzden doğru döndürür.
>> Yani biz sadece yüzeyi çizik var Şimdi bu veri yapılarının bazı.
Sorun beş set size olacak Yine başka bu keşfetmek,
ve tasarım verilecektir olacak Bu konuda nasıl bir seçim.
Ben sonuçlandırmak istiyorum Ne sadece 30 saniye teaser
ötesinde önümüzdeki hafta ve bekliyor ne.
>> Biz minnetle begin-- olarak, olabilir yavaş yavaş geçiş bence--
C ve alt dünyasından seviye uygulama detayları,
Bir dünya ki biz alabilir başkası nihayet sahip olduğu verilen
Bu veriler uygulanan Bizim için yapılar,
ve biz anlamak için başlayacağız gerçek dünya uygulama anlamına gelir
Web-tabanlı programlar ve web siteleri daha genel
ve ayrıca çok güvenlik biz sadece ettik etkileri
yuzeysel başladı.
İşte bizi bekliyor ne gün gelecek.
>> [VİDEO OYNATMA]
>> -O, Bir mesajla geldi Tüm kendi bir protokol ile.
O zalim bir dünyaya geldim güvenlik duvarları, yönlendiriciler uncaring,
ve tehlikeler ölümden çok daha kötü.
O hızlı.
O güçlü.
O, TCP / IP, ve o sizin adresinizi var.
"Net Warriors."
[SON VİDEO OYNATMA]
DAVID MALAN: önümüzdeki hafta geliyor.
Size daha sonra göreceğiz.
[VİDEO OYNATMA]
-Ve Şimdi, "Derin Düşünceler" DAV Farnham tarafından.
-David Hep başlar ile dersler "Tüm hakkı."
Neden, "İşte çözüm Bu haftaki sorunu kümesi "
ya da "Biz A hepiniz veriyorsun?"
[Gülüyor]
[SON VİDEO OYNATMA]