[MÜZİK OYUN]
HOPARLÖR 1: Pekala.
Herkes arka bölüme hoş geldiniz.
Hepinizin başarıyla umut senin sınav kurtarıldı
Geçen hafta.
Ben o zamanlarda biraz deli olduğunu biliyorum.
Sen eğer ben, daha önce söylediğim gibi standart sapma olan,
Gerçekten, özellikle, bu konuda endişelenmenize gerek yok daha az rahat bölüm için.
Yani olması gereken yerde hakkında.
>> Büyük yaptıysanız, o zaman müthiş.
Onur sana.
Ve hissediyorum eğer ihtiyacınız gibi biraz daha yardım, lütfen
ulaşmak için çekinmeyin TFs herhangi dışarı.
Hepimiz burada yardımcı olmaktır.
Biz öğretmek yüzden >> budur.
Senin için burada her Pazartesi olmamın nedeni budur Perşembe günleri çocuklar ve ofiste saat.
Yani bana bildirin çekinmeyin Eğer bir şey hakkında endişeleriniz varsa
veya quiz eğer bir şey var Bu gerçekten değinmek istiyorum.
>> Peki bugün için gündem tüm veri yapıları hakkında.
Bunlardan bazıları sadece sadece olacak Bu alışmak için.
Hiç uygulamak değil Bu sınıfta onları.
Olacak Bazıları, senin yazım pset için gibi.
>> Siz seçim olacak karma tablolar ve deneme arasında.
Bu yüzden kesinlikle bu üzerinde gidiyorum.
Bu tür kesinlikle daha olacak Bir üst düzey bölümünün bugün olsa,
çünkü orada onları bir yeri vardır, ve eğer Biz uygulama ayrıntıları gitti
Tüm bunlar, biz olmaz Hatta bağlı listeler yoluyla almak
ve belki de karma tabloları biraz.
>> Yani benimle ayı.
Biz yapıyor olacak değiliz kadar bu zaman kodlama.
Bu konuda herhangi bir sorunuz varsa ya da bunu uygulamaya görmek istiyorum
ya kendiniz deneyin, Ben kesinlikle tavsiye
, study.cs50.net olacak olan Bütün bunların örnekleri vardır.
Benim Powerpoints olacak notları ile biz
Bazı programlama gibi kullanma eğiliminde egzersizleri, özellikle şeyler için
bağlantılı listeler ve ikili gibi ağaçlar yığınları ve ipuçları.
Yani biraz daha yüksek düzeyde, hangi Sizin için güzel olabilir.
Bununla Böylece >> biz başlamak gerekir.
Ve ayrıca, evet-- sınavlar.
Ben sizin kim çoğu düşünüyorum Benim bölüm, sınavlar var
ama herkes ya nedense geliyor size yok, onlar burada ön konum.
>> Peki listeleri bağlantılı.
Gider ben bu tür biliyorum senin sınav öncesi geri.
Bu bir hafta önce oldu Biz bu konuda öğrendim.
Ancak bu durumda, sadece olacak derinlemesine biraz daha gidin.
>> Peki neden biz tercih olabilecek bir Bir dizi üzerinde listesini bağlantılı?
Onları farklı kılan nedir?
Evet?
>> İZLEYİCİ: Bir bağlantılı genişletebilirsiniz Bir dizinin sabit boyutta karşı listesi.
HOPARLÖR 1: Sağ.
Dizi ise boyutu sabit olan bağlantılı liste değişken boyuta sahiptir.
Biz bilmiyoruz Yani nasıl çok biz saklamak istiyoruz,
Bağlantılı bir liste bize büyük veriyor yol yapmak için biz sadece can çünkü
başka bir düğüme eklemek ve eklemek Başka bir düğüm ve başka bir düğüme ekleyin.
Ama ne bir ticaret-off olabilir?
Herkes ticaret-off hatırlıyor mu diziler ve bağlantılı listeler arasında?
Mmhmm?
>> İZLEYİCİ: Sen var tüm yol gitmek
bağlantılı liste içinde Bir listede bir öğe bulmak.
Bir dizide yapabilirsiniz sadece bir eleman bulmak.
>> HOPARLÖR 1: Sağ.
Yani arrays-- ile
>> İZLEYİCİ: [duyulamaz].
>> HOPARLÖR 1: Dizilerle birlikte, biz var Ne rasgele erişim denir.
İstersek ne demektir Bir listenin şimdiye beşinci noktası
veya beşinci nokta bizim Dizi, biz sadece yakalayabilir.
Bir bağlantılı liste varsa, biz var Doğru, yineleme için?
Yani bir eleman olarak erişme Bir dizi, sabit zaman
it would bağlantılı liste ile ise büyük olasılıkla çünkü belki doğrusal zaman
Bizim eleman sonunda tüm yoludur.
Biz her şeyi ile aramak zorunda.
Tüm bu verilerle Yani Biz gidiyoruz yapılar
biraz daha fazla zaman harcama için, artılar ve negatifleri nelerdir.
Biz isteyebilirsiniz zaman diğer üzerinden birini kullanın?
Ve bu tür büyük şey götürmek için.
>> Yani biz burada var Bir düğümün tanımı.
Bu bir elemanı gibi Bizim bağlantılı liste, değil mi?
Yani hepimiz tanıdık Bizim Typedef yapılar ile,
Biz son kez gözden gitti hangi.
Sadece yaratma Bu temelde biz-ebil kullanma başka bir veri türü.
>> Bu durumda, bir düğümün Bu bazı tamsayı yapacak.
Ve sonra ikinci bölüm burada ne var?
Herkes?
>> İZLEYİCİ: [duyulamaz].
>> HOPARLÖR 1: Evet.
Bir sonraki düğüme bir işaretçi var.
Yani bu aslında burada olmalı.
Bu tip bir gösterici Bir sonraki şey düğüm.
Ve bu ne var onlar Bizim düğümü kapsar.
Serin.
>> Pekala, biz gibi, arama ile çok sen eğer sadece elden önce diyerek
arama gidiyor, aslında yineleme var
Bağlantılı liste içinde.
Biz numara için arıyorsanız Yani 9, bizim başında başlamak istiyorum
ve o başında bize işaret Bizim bağlantılı liste, değil mi?
Ve tamam, bunu yapar, demek düğüm numarası 9 içeriyor?
Hayır mı?
>> Pekala, bir sonraki gidin.
Bunu takip edin.
Bu sayı 9 içeriyor mu?
Hayır.
Sonraki izleyin.
>> Yani biz aslında yineleme var Bizim bağlantılı liste içinde.
Biz sadece 9 olduğu doğrudan gidemez.
Ve siz gerçekten istiyorsanız Orada bazı sözde kod yukarı bakın.
Biz burada bazı arama fonksiyonu var o içinde sürer ne in-- alır?
Sen ne düşünüyorsun?
Çok kolay bir.
Bu nedir?
HEDEF KİTLE: [duyulamaz].
HOPARLÖR 1: aradığımız numara.
Doğru?
Ve bu ne tekabül eder?
Bu bir işaretçi değil mi?
>> İZLEYİCİ: Bir düğüm.
>> HOPARLÖR 1: listeye bir düğüm Doğru, bakıyoruz ki?
Bu yüzden bazı düğümler burada gösterici olan var.
Bu gidiyor bir noktadır aslında bizim listede yineleme.
Biz listelemek için eşit set bu sadece çünkü
için eşit ayarı Bizim bağlantılı liste başlar.
>> Ve NULL değil iken, süre biz hala bizim listede şeyler var
Bu düğüm olup olmadığını görmek için kontrol edin Aradığımız sayı.
Gerçek dön.
Aksi takdirde, doğru, güncellemek?
>> NULL ise, biz çıkmak bizim while döngüsü ve return false
anlamına gelir, çünkü biz onu bulamadım.
Herkes nasıl olsun mu?
TAMAM MI.
>> Ekleme ile Peki, üç farklı yol vardır.
Sen ekleyebilirsiniz, Önlerine çeşit çeşit içine ve ekleyebilirsiniz.
Bu durumda, konum Bir prepend yapacağız.
Herkes nasıl bu biliyor mu Üç olgu farklı olabilir?
>> Yani Başa eklenen sen koymak anlamına gelir listenizde önünde.
Yani demek istiyorum ki hiçbir konuda senin düğüm olursa olsun ne
değeri nedir, sen gidiyorsun Tamam, ön sağ buraya koymak için?
İlk olacak Listenizde eleman.
Eğer eklerseniz >> gidiyor Listenizde arkasına gitmek için.
Ve çeşit çeşit sen demek takın yerine aslında koyacaktım
bu tutar nereye bağlantılı liste sıralanır.
Yine, nasıl kullandığınız Bu ve ne zaman kullanmak
onları duruma göre değişir.
Bu gerek yoksa sıralanması, başına eğilimindedir
Ne çoğu insan olmak değil çünkü kullanmak
Tüm liste üzerinden gitmek zorunda Doğru, onu eklemek için sonuna bulmak için?
Siz sadece doğru bunu sopa.
>> Bu yüzden bir ile gidecek Ekleme 1 şimdi.
Ben gidiyorum Yani bir şey çok bu pset üzerinde tavsiye
Her zaman olduğu gibi, şeyler çekmektir.
Eğer güncellemeniz çok önemlidir Doğru sırayla işaretçileri
Eğer bunları güncelleştirmek çünkü eğer biraz bozuk,
Eğer sonuna kadar gidiyoruz Listenizde parçaları kaybetme.
>> Bu nedenle, örneğin, bu durumda biz konum 1 sadece noktaya başını söylüyorum.
Biz sadece yaparsak Bu 1 kaydetmeden,
hiçbir fikrim yok ne 1 şimdi işaret etmelidir
Kaybettiğimiz çünkü ne Baş işaret etti.
Yani bir şey hatırlamak ne zaman bir prepend yapıyoruz
ne kaydetmek için İlk kafa noktaları,
sonra yeniden atamak ve ardından güncelleme ne yeni bir düğüm işaret etmelidir.
Bu durumda, bu bunu yapmak için tek yoldur.
>> Biz bu şekilde yapmıştı Yani nerede biz sadece, kafa yeniden
biz temelde bizim, kaybetmek Tüm liste, değil mi?
Bunu yapmak için bir yolu 1 puan sahip olmaktır Bir sonraki ve daha sonra 1 baş noktası var.
Yoksa böyle bir tür yapabilirsiniz Ben hakkında konuştuk geçici depolama.
>> Ama, sizin yeniden atama Doğru sırayla işaretçileri
çok, çok olacak Bu pset için de gereklidir.
Aksi takdirde, bir karma için gidiyoruz tablo ya da sadece olacak bir deneyin
kelimelerin sadece bir parçası olduğunu sen Sen-- mmhmm sonra istiyor ve?
HEDEF KİTLE: Geçici neydi Depolama şey bahsediyorduk?
HOPARLÖR 1: Geçici depolama.
Yani temelde başka Eğer bu yapabileceğini yolu
gibi bir şey başkanı saklamanız o geçici değişken saklayın.
1 olarak atayın ve Daha sonra işaret 1 güncelleme
ne olursa olsun baş işaret için kullanılır.
Bu şekilde tabii ki daha şık size çünkü
Geçici bir değer gerekiyor, ama yok Sadece bunu yapmak için başka bir yol sunar.
Ve aslında var Bunun için bazı kod.
Bağlantılı listeye Yani, biz Aslında bazı kod var.
Yani bu prepending, buradan yerleştirin.
Yani bu başında o girer.
>> Peki ilk şey, size gerekir Elbette, yeni düğüm oluşturun,
ve NULL kontrol edin.
Her zaman iyi.
Ve sonra değerleri atamak gerekir.
Ne zaman, size yeni bir düğüm oluşturun sonraki işaret ne bilmiyorum,
böylece NULL için başlatmak istiyorum.
O bir şey işaret sona yoksa Başka, bu yeniden ve bunu gayet iyi olur.
Ilk şey ise Listede, ihtiyacı
Çünkü NULL işaret etmek Bu listenin sonu.
>> Öyleyse eklemek için, biz burada görmek Bizim düğümün sonraki değeri atama
başıdır ne olmak, hangi biz burada vardı ne.
Yani biz sadece yaptığımız buydu.
Ve sonra noktaya başını atıyorsanız Yeni düğüm, hatırlıyorum çünkü,
yeni bir düğüme bazı göstericidir ve bu tam olarak baş budur.
Bu tam olarak neden biz ise Bu ok erişimcisine var.
Serin?
Mmhmm?
>> İZLEYİCİ: biz var mı İlk NULL YENİ Sonraki başlatmak,
ya da biz sadece kafa için başlatılamıyor?
>> HOPARLÖR 1: Bir sonraki Yeni başlatmak için NULL olması gerekir
Eğer bilmiyorum çünkü nerede olacak.
Ayrıca, bu tür bir Sadece bir paradigma gibi.
Bunu NULL eşit adil yapmak için ayarlanır emin tüm üsleri kapalı olduğu
Eğer ki herhangi bir atanmakla yapmadan önce Eğer her zaman olacak garanti ediyoruz
belirli bir değere işaret olabilir Bir çöp değer gibi karşı.
Evet, biz atamak, Çünkü otomatik olarak bir sonraki yeni,
ama sadece bir gibi daha var iyi uygulama bunu başlatmak için
bu şekilde ve daha sonra yeniden atayın.
>> Tamam, bu yüzden iki kat şimdi listeleri bağlantılı.
Ne düşünüyorsunuz?
Ne ile farklı çift ​​listeleri bağlantılı?
>> Bizim bağlı listelerde Yani, biz Sadece doğru, tek yönde hareket?
Biz sadece bir sonraki var.
Biz sadece ileriye gidebiliriz.
>> Bir çift bağlantılı liste ile, biz de geriye doğru hareket edebilir.
Bu yüzden sadece var Biz saklamak istediğiniz sayı,
sonraki işaret nerede var ve biz sadece nereden geldiğini.
Yani bu sağlar biraz daha iyi kastetmek.
>> Yani çift bağlı düğüm çok benzer, değil mi?
Tek fark, biz şimdi Bir sonraki ve bir önceki var.
Sadece fark bu.
>> Bu yüzden prepend veya biz append-- olsaydı ötürü-- bunun için herhangi bir kodu yok
ama denemek olsaydı ve önemli bir şey takın
Yapmanız gereken ise emin atıyorsanız
hem senin, önceki ve hesabınızla Doğru sonraki işaretçi.
Yani bu durumda, olur sadece bir sonraki başlatılamadı,
Önceki başlatılamıyor.
Biz listenin başında iseniz, biz Baş eşit yeni yapacağı değil, sadece,
ama bizim yeni bir önceki gerekir Doğru, baş işaret?
>> Bu sadece fark bu.
Ve daha pratik istiyorsanız yerleştirme ile bağlantılı listeler, bu,
insert ile, silerek Bir çeşit çeşit listesine,
study.cs50.net kontrol ediniz.
Büyük egzersizleri bir grup var.
Bunları tavsiye ederim.
Ben onlara geçmesi için zaman olsaydı ama veri yapılarının bir çok şey var
aracılığıyla almak için.
>> Tamam, karma tabloları yüzden.
Bu muhtemelen en çok hakkında pset için yararlı biti
Burada olmak için gidiyoruz çünkü Bunlardan birini, ya da bir deneyin uygulanması.
Ben gerçekten hash tabloları seviyorum.
Onlar oldukça serin olduğunu.
>> Yani temelde ne olur bir karma tablo
biz gerçekten hızlı ihtiyacım olduğunda ekleme, silme ve arama.
Bu bizim konum şeyleri vardır bir karma tablo öncelik.
Onlar, oldukça büyük alabilirsiniz ama biz denemeden ile göreceğimiz gibi,
çok daha büyük şeyler vardır.
>> Ama temelde, bütün bir karma tablo karma işlevi
her koymak hangi kova söyler verilerinizin, sizin elemanların her biri.
Basit bir yolu, bir karma tablo düşünmek şeylerin sadece kovalar olmasıdır,
değil mi?
Güvenebileceğiniz şeyler sıralama vardır Peki ne zaman kendi adının ilk harfi gibi,
Bu tür bir karma tablo gibi.
Ben grup olsaydı Yani >> siz olduğunu 's isim başlar kim gruplar halinde
Burada bir ile, ya da doğum günü kim var Ocak, Şubat, Mart ayında ise
ne olursa olsun, bu etkili bir olduğunu Bir karma tablo oluşturma.
Sadece kovaları yaratıyor ki Eğer içine öğeleri sıralamak
Eğer onları daha kolay bulabilirsiniz böylece.
Ben gerekir bu yolla Yani Senin birini bulmak için,
Ben aramak zorunda değilsiniz senin isimlerin her biri ile.
Oh gibi olabilir, ben biliyorum Danielle doğum günü in-- olduğunu
HEDEF KİTLE: --April.
HOPARLÖR 1: Nisan.
Yani benim Nisan bakmak kova ve herhangi bir şans ile,
o sadece bir tane olacak ve Benim zaman, bu anlamda sürekli oldu
Ben bakmak varsa oysa insanlar bir sürü ile,
çok daha uzun zaman alacak.
Yani hash tabloları gerçekten sadece kovalar.
Kolay bir şekilde onları düşünmek.
Hakkında >> Yani çok önemli bir şey Bir karma tablo karma fonksiyonudur.
Yani işler Ben gibi, hakkında konuştuk İlk adının ilk mektup
ya da doğum ay, Bu fikirler olduğunu
Gerçekten bir karma işlev ile bağlantılıdır.
Bu karar sadece bir yolu var ki Tamam, konum eleman gider kova?
Yani bu pset için, yukarı bakabilirsiniz İstediğiniz herhangi bir hash fonksiyonu oldukça fazla.
>> Kendi olmak zorunda değil.
Bazı gerçekten harika olanları vardır çılgın matematik her türlü orada yapmak olduğunu.
Ve sen, sizin yapmak istiyorsanız süper hızlı imla kontrolü,
Ben kesinlikle olur Bunlardan birine bakmak.
>> Ama aynı zamanda orada hesaplamak gibi basit olanlar,
kelimelerin, toplamı gibi Her harf bir numarası vardır.
Toplamını hesaplayın.
O kovayı belirler.
Onlar da kolay olanları var Sadece bir buradan tüm gibidir,
B hepsi burada.
Bunlardan herhangi biri.
>> Temelde, sadece size söyler hangi dizi indeksi içine gitmeli senin eleman.
Sadece bucket-- karar hepsi bir hash fonksiyonu olduğunu var.
Yani burada biz bir örnek var dize sadece ilk harf
ben sadece bahsediyordum.
>> Yani sadece var bazı karma var dize eksi A ilk harfi,
bazı verecek olan 0 ile 25 arasında sayı.
Ve ne yapmak istiyorum Bu temsil emin olun
senin karma boyutu table-- Kaç kovalar vardır.
Bu birçok ile hash fonksiyonları, onlar
gidiş o olabilir değerler iade edilecek çok kovalar sayısının üzerinde olması
aslında var senin karma tablo,
böylece yapmak gerekir Emin ve kişiler tarafından mod.
Aksi takdirde, söyleyecek, oh, bu kova 5.000 olmalıdır
ama sadece 30 var senin karma tablo kovalar.
Ve tabii ki, hepimiz biliyoruz Bazı çılgın hatalara neden olacak.
Yani tarafından mod emin olun senin karma tablo boyutu.
Serin.
Çarpışmalar Yani.
Herkes kadar iyi midir?
Mmhmm?
>> İZLEYİCİ: Neden olur Böyle büyük bir değer döndürür?
>> HOPARLÖR 1: algoritmasına bağlı olarak senin hash fonksiyonu kullanır.
Bazıları yapacak çılgın çarpma.
Ve alma hakkında hepsi Bir hatta dağıtım,
bu yüzden gerçekten bazı şeyleri bazen çılgınca şeyler.
Hepsi bu.
Başka herhangi bir şey?
TAMAM MI.
>> Çarpışmalar Yani.
Temelde, daha önce söylediğim gibi, En iyi senaryoya göre,
Ben içine bakmak herhangi bir kova bir şey olacak,
bu yüzden doğru, hiç bakmak zorunda değilsiniz?
Ben de orada olduğunu biliyorum ya da var değil, ve biz gerçekten ne istediğinizi.
Ama biz on binlerce varsa veri noktaları ve bu sayı daha az
kovalar, biz gidiyoruz çarpışmalar nerede sonunda bir şey
Bir de sonuna kadar sahip oluyor Zaten bir unsuru vardır kova.
>> Yani soru, ne biz bu durumda yaparsınız?
Ne yapacağız?
Biz zaten orada bir şey var mı?
Biz sadece dışarı atmak mı?
>> Hayır
Biz ikisini de tutmak zorunda.
Yani yol ki tipik olarak ne yapmak?
Veri yapısı nedir biz sadece konuştuk?
HEDEF KİTLE: Bağlantılı listesi.
HOPARLÖR 1: Bir bağlantılı liste.
Yani şimdi, yerine bu her kovalar sadece bir elemanı olan
o bir bağlantılı liste içeren gidiyor içine karma edildi unsurlar.
Tamam, herkes tür fikrini alır?
Biz bir dizi var olamazdı, çünkü Biz ne çok şey bilmiyorum çünkü
Orada olacak.
Bağlantılı liste için bize izin verir sadece tam sayı olması
Doğru, o kovaya karma edilir?
>> Peki doğrusal sondalama olduğunu temelde bu iyi düşünce
Bir çarpışma ile başa çıkmak için tek yolu.
Ne yapabilirim bu, eğer bir durumda, dut 1 içine karma edildi
ve biz zaten var bir şey var, sadece
kadar aşağı devam Boş bir yuva bulmak.
İşte bu işlemek için tek yoldur.
işlemek için başka bir yol onunla ne biz sadece
bağlantılı called-- Liste zincirleme denir.
>> Yani bu fikir çalışır Sizce sizin karma tablo
çok daha büyüktür veri ayarlamak veya eğer
deneyin ve zincirleme en aza indirmek istiyorum kesinlikle gerekli olana kadar.
Yani bir şey lineer Açıkçası demektir sondalama
senin hash fonksiyonu olduğunu oldukça kullanışlı değil
Kullandığınız sonuna kadar gidiyoruz çünkü senin karma işlevi, bir noktaya almak,
Eğer aşağı soruşturma doğrusal Mevcut bazı yer.
Ama şimdi, tabii, bir şey , orada biter başka
Eğer zorunda gidiyoruz daha aşağı arama.
>> Ve daha bir çok var Arama gider o
Bir eleman girerek gider Şimdi karma tablo, değil mi?
Ve şimdi gidip çalışın ve bulduğunuzda berry tekrar bunu karma gidiyoruz,
ve o söyleyecek oh, kova 1 bakmak,
ve olacak değil kova 1, bu yüzden sen
çapraz zorunda olacak Bu geri kalanı ile.
Bu yüzden, bazen yararlıdır ancak çoğu durumda,
Biz söylemek için gidiyoruz zincirleme yapmak istediğiniz şeydir.
>> Peki bu daha önce konuştuk.
Kendime küçük bir ahead var.
Ama zincirleme temelde olduğunu senin karma tablo her kova
Sadece bir bağlantılı liste.
>> Peki başka bir yol, ya da daha teknik yol, bir karma tablo düşünmek
sadece bir dizi olmasıdır bağlantılı listeler, hangi
ne zaman sözlüğü yazıyoruz ve bunu yüklemek için çalışıyoruz,
Bir şekilde bunu düşünme bağlantılı listeler dizisi
çok daha kolay hale getirecek Başlatmak için.
>> İZLEYİCİ: Yani karma tablo önceden tespit edilmiş bir büyüklüğe sahip olan
kovalar bir [Inaudible] gibi?
>> HOPARLÖR 1: Sağ.
Bu yüzden bir dizi numarası vardır Eğer determine-- kovalar
hangi çocuklar gerektiğini ile oynamak için çekinmeyin.
Bu oldukça serin olabilir ne olacağını görmek için
Eğer kova sizin sayısını değiştirmek gibi.
Ama evet, sahip olduğu bir kovalar set sayısı.
Ne kadar uyum sağlar İhtiyacınız kadar birçok unsurlar
Bu ayrı zincirleme nereye olduğunu Her kova listeleri bağlantılı olması.
Bu senin karma tablo anlamına gelir tam boyut olacak
Eğer doğru olmasını gerektiğini?
Yani bağlantılı listelerin bütün mesele bu.
Serin.
>> Orada Böylece herkes tamam?
Tamam.
Ah.
Ne oldu?
Gerçekten şimdi.
Biri beni öldürüyor sanırım.
>> Tamam biz gitmek için gidiyoruz Biraz deli çalışır.
Ben hash tabloları seviyorum.
Ben onlar gerçekten harika olduğunu düşünüyorum.
Denemeleri çok serin.
>> Yani herkes bir deneyin ne hatırlıyor mu?
Sen üzerine gitmiş olmalı kısaca derste?
Eğer nasıl çalıştığını tür hatırlıyor musunuz?
HEDEF KİTLE: Ben sadece başını sallayarak ediyorum Biz bitti gitti ki.
HOPARLÖR 1: Biz bitti gidin.
Tamam, biz gerçekten gitmek için gidiyoruz şimdi olduğu üzerinde biz dediklerini.
>> İZLEYİCİ: Bu bir alma ağacı var.
>> HOPARLÖR 1: Evet.
Bu bir alma ağacı.
Korku.
Yani burada fark bir şey olduğunu biz bireysel karakter bakıyorsun
Burada, değil mi?
>> Yani birlikte önce hash fonksiyonu, biz Bir bütün olarak kelime aradılar,
ve şimdi daha arıyoruz karakter, değil mi?
Yani biz burada ve Mendel üzerinde Maxwell var.
Yani temelde bir try-- bir yol düşünmek Bu konuda her seviyede burada
harflerin bir dizidir.
Yani bu kök düğüm doğru, burada mı?
Bu bütün karakterler var Her kelimenin başlangıcı için alfabe.
>> Ve ne yapmak istiyorum diyelim ki, tamam, biz bazı M kelime var.
Biz Maxwell aramaya gidiyoruz, bu yüzden konum Biz bütün M. Ve M noktalara gitmek
Diğer bir dizi her yerde sürece orada kelime,
A olan bir kelimedir İkinci mektup gibi,
sürece bir kelime orada olduğu gibi İkinci mektup gibi B vardır,
Bir işaretçi olacak Bazı sonraki diziye gidiyor.
>> Muhtemelen bile yok kelimesi MP şey,
Bu P konumunda yani Dizi, sadece null olur.
Hiçbir kelime yoktur, tamam, derdi Bu M Tamam, bir P tarafından takip etti?
Yani biz bu, her biri hakkında düşünüyorsanız Bu küçük şeylerden biri
Aslında bunlardan biridir Z. aracılığıyla A büyük diziler
Yani şeylerden biri ne olabilir bir deneyin bir dezavantajı tür?
>> İZLEYİCİ: belleğin bir sürü.
>> HOPARLÖR 1: Sağ, belleğin bir ton var?
Burada bu blokların her biri 26 boşluk, 26 eleman dizisini temsil eder.
Yani çalışır uzay ağır inanılmaz olsun.
>> Ama çok hızlı.
Yani inanılmaz hızlı ama Gerçekten uzay verimsiz.
Tür anlamaya var hangisinin istediğiniz.
Bunlar, sizin pset için gerçekten harika ama onlar bellekte bir sürü almak yapmak,
böylece kapalı ticaret.
Evet?
>> İZLEYİCİ: bu mümkün olabilir mi Daha sonra bir deneyin kurmak ve
Eğer bir kez tüm Eğer need-- that veri
Mantıklı olurdu bilmiyorum.
Ben kurtulmak oldu tüm NULL karakter, ama sonra
Eğer endeks them-- mümkün olmaz
>> HOPARLÖR 1: Hala onlara ihtiyacımız var.
>> İZLEYİCİ: - aynı şekilde her zaman.
HOPARLÖR 1: Evet.
Sen izin boş karakter gerekir Orada bir kelime yok eğer bilirsin.
Eğer istediğiniz bir şey var Ben mı?
TAMAM MI.
Pekala, bu yüzden gidiyoruz Biraz daha gitmek
arkasında teknik detaya Bir deneyin ve bir örnek üzerinde çalışalım.
>> Tamam, bu yüzden bu aynı şeydir.
Bağlantılı bir listede, Bizim ana Oysa ? tür of-- istediğim kelime ne -
blok bina gibi bir düğüm oldu.
Bir deneyin, biz de, bir düğüm var ama farklı tanımlanmış oluyor.
>> Bu yüzden bazı bool var Bir kelime olsun aslında temsil
Bu konumda bulunmaktadır, ve sonra biz ötürü-- doğrusu bazı dizi var
Bu bir bir gösterici 27 karakter dizisi.
Ve bu, bu durumda, içindir 27-- Hepinize gibi eminim, bekle
alfabede 26 harf vardır.
Neden 27 var mı?
>> Yani bağlı Eğer bu uygulamak yolu,
Bu pset ait olduğunu kesme için izin verdi.
Yani bu yüzden ekstra biri.
Ayrıca bazı olacak olgular boş sonlandırıcı
olarak dahil edilmiştir o izin var karakterleri,
ve onlar kontrol nasıl bu kelimenin sonu olmadığını görmek.
Eğer ilgileniyorsanız, check out Study.cs50 üzerine Kevin'in video,
yanı sıra Vikipedi olduğu gibi Orada bazı iyi kaynaklar.
>> Ama biz sadece tür gitmek için gidiyoruz Bir deneyin aracılığıyla işe yarayabilecek nasıl
Eğer verilir eğer.
Yani biz burada bir süper basit bir tane var Onlara kelimeler "yarasa" ve "zoom" vardır.
Ve biz burada gördüğünüz gibi, Burada bu küçük alan
Bizim BOOL temsil eder evet, bu bir kelime, diyor.
Ve sonra bu bizim, sahip karakter dizileri, değil mi?
>> Yani biz aracılığıyla gidecek Bu denemede "yarasa" bulma.
Yani doğru, üstünde başlar?
Ve biz b karşılık geldiğini biliyorum İkinci endeksi, ikinci eleman
Bu dizide, a ve b çünkü.
Yani yaklaşık olarak ikinci bir.
>> Ve Tamam, içine serin izleyin diyor Bir sonraki dizi, biz hatırlıyorum çünkü eğer,
bu bölgesinin her değil Aslında elemanı içerir.
Bu dizilerin her biri bir Doğru, bir gösterici içerir?
Bunu yapmak için önemli bir ayrım var.
>> Ben bu çalışır olan şey olmak gidiyor biliyorum ilk kez almak gerçekten zor,
bu nedenle bu olsa bile İkinci ya da üçüncü kez
ve bu tür hala zor görünüşteki,
Eğer izlemek giderseniz ben söz veriyorum kısa yarın tekrar,
muhtemelen çok daha mantıklı olacak.
Bu sindirmek için bir sürü alır.
Ben hala bazen duyuyorum gibi, bekle, bir deneyin nedir?
Ben bu nasıl kullanabilirim?
>> Peki bu durumda b var, hangi bizim ikinci endeksidir.
Biz olsaydı, diyelim ki, c veya d veya başka herhangi bir harf,
Biz dizine arkanı harita gerekir Bizim dizinin edilene karşılık gelir.
Bu yüzden rchar gibi alacağını ve sadece biz Bir 0-25 içine haritaya kapalı çıkarma.
İyi Herkes nasıl biz Bizim karakterleri map?
TAMAM MI.
>> Bu yüzden ikinci bir ve biz gitmek görmek, evet, bu NULL değil.
Biz bu sonraki diziye hareket edebilirsiniz.
Yani biz burada bu sonraki diziye devam.
>> Ve şimdi, tamam, demek biz bir burada olmadığını görmek gerekir.
Bir null veya yok aslında ileriye taşımak?
Yani aslında bir hamle Bu dizide ileri.
Ve biz Tamam, t son harfi, söylüyorlar.
Yani biz dizinindeki t gitmek.
Ve sonra biz ileriye taşımak çünkü başka bir tane var.
Ve bu, evet, temelde söylüyor o bir kelime olduğunu söylüyor ötürü--
Eğer bu izlerseniz, o yol, sen gelmiş
Bir kelime, biz biliyoruz ki "yarasa" dir.
Evet?
>> İZLEYİCİ: standart olduğunu var mı Daha sonra endeksi 0 ve 1 gibi bir tür var
veya sonunda var mı?
>> HOPARLÖR 1: Hayır
Biz geriye bakmak Yani eğer bizim Burada beyan, bu bir bool var,
bu yüzden sizin düğüm kendi unsur var.
Bu yüzden dizinin parçası değil.
Serin.
Bizim kelime bitirmek ve Yani biz konum Bu dizi, biz ne istiyoruz
Bu bir kelime için bir kontrol yapmak olduğunu.
Bu durumda, evet dönüş olur.
>> Peki o notta, biz bu "hayvanat bahçesi" know - "Hayvanat Bahçesi" bir kelime olduğunu insanlarda gibi biz biliyoruz
değil mi?
Ama burada olur deneyin hayır, o değil, diyorum.
Ve o söyleyebilirim çünkü biz Burada bir kelime olarak belirlenmiş değil.
Hatta biz çapraz olsa Bu dizi aracılığıyla,
Bu deneyin, hayır, söyleyebilirim zoo sizin sözlükte değil
biz var çünkü gibi belirlemiştir.
>> Yani tek yönlü ki- yapmak ah, üzgünüm, bu bir.
Yani bu durumda, "hayvanat bahçesi" değildir Bir kelime, ama bizim denemede olduğunu.
Ama bu birinde, biz bunu istiyoruz ki "banyo" ne olur kelimeyi tanıtmak
Biz through-- b, bir, t takip etmektir.
Biz bu dizide konum ve biz h aramak için gidin.
>> Bu durumda, ne zaman h işaretçi bakmak,
Tamam, NULL işaret ediyor?
Açıkça bu sürece Başka bir dizi işaret,
Eğer farz tüm işaretçileri ki Bu dizide null işaret ediyor.
Bu durumda Yani, h işaret biz bir şey yapamayız yani null,
bu yüzden de dönecekti sahte, "banyo" Burada değil.
Yani şimdi biz aslında konum ile gidecek
nasıl biz aslında söyleyebilirim Bu "Hayvanat Bahçesi" Bizim denemede olduğunu.
Nasıl bizim denemede içine "hayvanat bahçesi" ekleyebilirim?
Biz başladık, aynı şekilde çok Bizim bağlantılı liste, biz kökünde başlar.
Şüphe, en başladığınızda Bunların kökü.
>> Ve biz söyleyeceğim, tamam, z.
z bu var, ve öyle.
Yani üzerine gidiyoruz sonraki dizi, tamam mı?
Ve sonra bir sonraki üzerine, tamam, o mevcut mu demek?
It does.
Bu yine.
>> Ve böylece bizim bir sonraki, biz dedi ettik, Tamam, "hayvanat bahçesi" zaten burada var.
Yapmamız gereken tek şey, bu eşit ayarlanır true, orada bir kelime olduğunu.
Her şeyi takip olsaydı Bu noktadan önce kadar,
o, bir kelime yüzden sadece Böyle için eşit ayarlayın.
Evet?
>> İZLEYİCİ: Öyleyse bunu yapar "ba" bir kelime de olduğu anlamına gelir?
>> HOPARLÖR 1: Hayır
Yani bu durumda, "ba" Biz alacağı Burada, biz, bir kelime olduğunu söyleyebilirim
ve hala hiçbir olurdu.
TAMAM MI?
Mmhmm?
>> İZLEYİCİ: Eğer bir kez Yani bir kelime ve o zaman, evet demek
m gitmek içerecektir?
>> HOPARLÖR 1: Yani bu yapmak zorunda Şarkı söylemeyi kes Eğer bu yükleniyor ediyoruz.
Siz "Hayvanat Bahçesi" bir kelime olduğunu söylüyorlar.
Eğer check-- gittiğinizde gibi, sen söylemek istiyorum ki,
"Hayvanat Bahçesi", bu sözlükte mevcut mu?
Sadece ", hayvanat bahçesi" aramak için gidiyoruz ve sonra bir kelime olup olmadığını görmek için kontrol edin.
Sen hiç hareket için gidiyoruz bu değil, çünkü m kadar
ne için arıyoruz.
>> Biz aslında istedim Yani eğer Bu denemede içine "banyo" add,
Biz de aynı şeyi yapacağını biz yaptığımız gibi "hayvanat bahçesi"
ne zaman biz o görürdünüz dışında denemek ve h olsun, o yok.
Çalışırken Yani bu düşünebilirsiniz Bir bağlantılı listeye yeni bir düğüm eklemek için,
bu yüzden başka eklemeniz gerekir böylece gibi bu dizilerin biri.
Ve sonra biz sadece h ayarlanır biz ne Bu işaret, bu dizinin elemanı.
>> Ve sonra ne biz burada yapmak istersiniz?
True eşit ekle çünkü bir kelime.
Serin.
Biliyorum.
Denemeleri değil en heyecan verici.
İnan bana, ben biliyorum.
>> Yani bir şey denemeden ile gerçekleştirmek, Ben çok verimli olduğunu söyledi.
Bu yüzden onlar gördüm alan bir ton kadar sürebilir.
Onlar tür karıştırıyorsun.
Peki neden biz hiç bu kullanmak?
Onlar çünkü biz bu kullanmak inanılmaz etkili.
>> Yani eğer hiç arıyorsanız Bir kelime kadar, sen sadece
kelime uzunluğu ile sınırlanır.
Yani bir arıyorsanız uzunluk beş kelimesi,
Eğer sadece hiç zorunda gidiyoruz Tamam, en fazla beş kıyaslamalara yapmak?
Yani temelde bir sabit kılar.
Ekleme ve arama gibi temelde sabit zaman vardır.
>> Hiç alabilirsiniz Yani eğer sabit zamanda bir şey,
o gets kadar iyi.
Sen daha iyi alınamıyor Bu şeyler için zaman sabiti.
Böylece biridir denemeden büyük artılar.
>> Ama alan bir çok şey var.
Yani bir tür karar vermek zorunda sana ne daha önemli.
Ve bugünün bilgisayarlarda, alan bir deneyin kadar sürebileceğini
Belki de etkilemez o kadar, ama belki
Eğer bir şey ile uğraşıyoruz Bu, çok, çok daha fazla şeyler vardır
ve bir deneyin sadece makul değil.
Evet?
>> İZLEYİCİ: Bekleyin, böylece 26 var her biri mektuplar?
>> HOPARLÖR 1: Mmhmm.
Evet, sen 26 var.
Bazı sonra kelime işareti ve bir var her biri 26 işaretçiler var.
Ve onlar point-- konum
>> İZLEYİCİ: Ve her 26, her 26 var mı?
>> HOPARLÖR 1: Evet.
Olabildiğince Ve bu, bu yüzden oldukça hızlı genişler, bkz.
Tamam.
Bu yüzden, ağaçların içine almak için gidiyoruz hangi Sevdiğim kolay hissediyorum ve muhtemelen olacak
Bir güzel küçük ertelemek olmak Orada denemeden gelen.
Yani umarım çoğunuz daha önce bir ağaç gördük.
Güzel gibi değil dışında olanlar, ki ben
Herkes bilmiyorum Son zamanlarda açık havada gitti.
Ben elma bu hafta sonu toplama gitti, ve aman oh güzel oldu.
Ben yaprakları bilmiyordum O güzel görünebilir.
>> Peki bu doğru, sadece bir ağaç nedir?
Sadece bazı düğüm var, ve diğer düğümlerin bir demet işaret.
Burada gördüğünüz gibi, bu yinelenen tema tür.
Düğümlerine Düğümler işaret tür bir Birçok veri yapılarının özü.
Sadece biz nasıl bağlıdır Onları birbirlerine işaret var
ve nasıl hareket içlerinden ve nasıl
belirlerse şeyleri eklemek Farklı özellikleri.
>> Yani sadece bazı terminoloji, ki ben daha önce kullandım.
Yani kök çok üstünde ne olursa olsun.
biz her zaman başlangıç ​​nerede var.
Ayrıca kafa olarak düşünebiliriz.
Ama ağaçlar için, biz eğilimindedir root olarak bakın.
>> Altındaki şey ötürü-- Çok, çok bottom-- de
kabul yaprakları vardır.
Yani onunla birlikte gider Bütün ağaç şey, değil mi?
Yapraklar ağacın kenarlarında bulunmaktadır.
>> Ve o zaman biz de bir çift var terimleri ilgili düğümler hakkında konuşmak
birbirlerine.
Bu yüzden, ebeveyn var Çocuklar ve kardeşleri.
Bu nedenle, bu durumda, 3 5, 6 ve 7, ana.
Yani üst ne olursa olsun bir sen ne yukarıda bir adım
yani sadece atıfta Bir aile ağacı gibi.
Umarım, bu tüm biraz Bit deneme daha sezgisel.
>> Kardeşler sahip herhangi bir maddedir Sağ aynı ana,?
Burada aynı seviyede konum.
Ve sonra ben, olduğu gibi diyerek, çocuklar sadece vardır
Aşağıda bir adım ne olursa olsun Söz konusu düğüm, tamam mı?
Serin.
Yani bir ikili ağaç.
Herkes birinde bir tahminde Can İkili ağacın özellikleri?
>> İZLEYİCİ: Maksimum iki yaprak.
>> HOPARLÖR 1: Sağ.
Yani iki yaprak maks.
Yani daha önce bu birinde, biz bu vardı Bu, üç vardı, ama bir ikili ağaç
Eğer ikisinin max var ebeveyn başına çocuk, değil mi?
Başka var ilginç bir özelliği.
Herkes biliyor mu?
İkili ağaç.
>> Yani bir ikili ağaç her şey olur Şeyin bu bir sorted-- değil
ama sıralı ikili ağaç, Sağdaki şeyi
, ebeveyn büyüktür ve soldaki her şeyi
ana daha azdır.
Ve bu bir sınav olmuştur Soru önce, çok iyi bilmek.
Yani biz bu tanımlayan yol, Yine, biz başka bir düğüm var.
Bu ne çok benziyor?
Iki misli
>> İZLEYİCİ: Bağlı listeler
>> HOPARLÖR 1: Bir çift bağlantılı liste, değil mi?
Yani biz bu değiştirirseniz önceki ve sonraki ile,
Bu bir çift bağlantılı liste olacaktır.
Ancak bu durumda, biz aslında sol ve sağ ve bu kadar var.
Aksi takdirde, tam olarak aynı.
Biz hala elemanı var Eğer aradığınız
ve sadece iki işaretçiler var ne olursa olsun gidiyor yanında.
Evet, bu yüzden ikili arama ağacı.
Biz, her şeyi fark ederseniz Burada büyük edemememden olduğunu
hemen veya her Burada sağa
Her şey daha büyüktür Burada daha azdır.
>> Bu yüzden arama olsaydı, onu İkili arama çok yakın bakmak gerekir
Burada, değil mi?
Yerine bakarak dışında Yarım dizisinde,
Biz sadece iki solunda arıyoruz Yan ya da ağacın sağ tarafında.
Biraz basit olur Yani, sanırım.
>> Kök NULL Yani, Açıkçası sadece yanlış değil.
O varsa ve tabii ki bu doğru.
O daha az ise, biz sol arama.
O daha büyük ise, Biz hakkımız arayın.
Bu, tam olarak ikili arama gibi sadece farklı bir veri yapısı
biz kullanıyoruz.
Bunun yerine bir dizi, sadece bir ikili ağaç.
>> Tamam, yığınları.
Ve aynı zamanda, biz gibi görünüyor zaman biraz olabilir.
Bunu yaparsak, ben gitmek için mutluyum Bu herhangi bir tekrar.
Tamam, bu yüzden yığınlar.
Herkes ne hatırlıyor mu stacks-- Bir yığının herhangi bir özellikleri?
>> Tamam, çoğumuz bu yüzden, sanırım, yemek yemek halls--
biz gibi olmayabilir kadar.
Ama belli ki, bir yığının düşünebilirsiniz anlamıyla sadece tepsileri bir yığını olarak
veya şeylerin bir yığın.
Ve ne önemli gerçekleştirmek için bu olmasıdır
karakteristik şey-- biz by-- diyoruz ki LIFO olduğunu.
Herkes bu açılımı ne biliyor mu?
Mmhmm?
>> İZLEYİCİ: ilk, dışarı Last.
>> HOPARLÖR 1: Sağ, ilk olarak, dışarı sürer.
Bildiğimiz Yani, biz şeyleri istifleme eğer yukarı, en kolay şey off-- kapmak için
ve belki de tek şey yakala Bizim yığını büyük enough-- ise kapalı
Bu üst unsurdur.
Yani ne olursa olsun konulmuştur Burada gördüğünüz gibi last--,
ne olursa olsun itildi çoğunda recently-- olduğunu
İlk olacak Biz kapalı pop şey, tamam mı?
>> Peki biz burada var olduğunu Başka bir typedef struct.
Bu gerçekten sadece bir gibi olduğunu veri yapısı kursu çökmesine,
böylece çocuklar atılan bir çok şey var.
Biliyorum.
Yani başka bir yapı.
Yapıların Yay.
>> Bu durumda, bir işaretçinin Bazı kapasiteye sahip bir dizi.
Yani bu bizim yığını temsil Burada, bizim gerçek dizi gibi
bizim elemanları tutuyor.
Ve sonra burada bazı boyutu var.
>> Ve genellikle, saklamak istediğiniz yığını ne kadar büyük iz
bu izin ne oluyor çünkü Eğer boyutu biliyorsanız yapmak için,
Eğer söylemek için izin verir, Tamam, ben kapasitede olduğumu?
Ben daha fazla bir şey ekleyebilir miyim?
Ve o da size söyler nerede yığının üst
öylesine sizi biliyorum Aslında çıkarabilirsin.
Ve aslında gidiyor Burada biraz daha net.
>> Peki itme, bir şey için, eğer itme uygulamak için hiç vardı,
Ben sadece söylediğim gibi, sizin yanınızdaki yığını sağ, sınırlı bir boyutu vardır?
Bizim dizi bazı kapasiteye sahip.
Bu bir dizi var.
Bu sabit bir boyutu olduğunu, bu yüzden gerek daha fazla koyarak değil emin olun
biz daha bizim diziye Aslında için yer var.
>> Yani bir itme oluştururken fonksiyonu, tamam, diyelim ki yapmak ilk şey,
Benim yığını boşluk var mı?
Ben yapmazsam, üzgünüm Çünkü Ben senin elemanı saklayamazsınız.
Ben yaparsanız, o zaman saklamak istediğiniz bu yığının üstündeki, değil mi?
Elimizdeki neden >> Ve bu Bizim boyutu takip etmek.
Bizim boyut takip etmezseniz, bunu koymak nerede bilmiyorum.
Biz ne çok şey bilmiyorum Zaten bizim dizi bulunmaktadır.
Açıkçası gibi yolları vardır belki bunu yapabilirdi.
Sen NULL için her şeyi başlatmak olabilir ve daha sonra son NULL kontrol,
ama bir daha kolay şey sadece bir Tamam, büyüklüğü takip söylemek.
Ben biliyorum gibi ben dört elementin var Benim dizide, bir sonraki şey çok
biz koymak, biz konum endeksi 4 de saklamak için gidiyoruz.
Sonra, tabii ki, bu demektir Eğer başarılı bir şey itti ettik
senin yığına, sen boyutunu artırmak istiyor
biliyorum ki bunu nerede Eğer daha fazla şeyler itebilir ki.
>> Biz pop çalışıyoruz Yani eğer yığın kapalı bir şey,
ilk şey ne olabilir biz kontrol etmek istediğiniz?
Sen almaya çalışıyoruz senin yığın kapalı bir şey.
Emin var mı destenizin şey?
Hayır.
Peki ne kontrol etmek isteyebilirsiniz?
>> İZLEYİCİ: [duyulamaz].
HOPARLÖR 1: boyutu mı?
Boyutu.
Yani biz olmadığını görmek için kontrol etmek istediğiniz bizim boyut Tamam, 0'dan büyüktür?
Ve eğer, o zaman azaltmak istiyoruz 0 ile bizim boyut ve dönüş.
Neden?
>> İlk birinde biz iterek, biz itti
boyutu ve daha sonra güncellenmiş boyutu üzerine.
Bu durumda, boyut azaltma konum ve sonra koparma, havalandığını
Bizim diziden.
Neden biz bunu olabilir?
Yani benim yığın üzerinde bir şey varsa, Bu noktada benim boyutu ne olurdu?
1.
>> Ve nerede eleman 1 saklanır?
Ne endeksi at?
HEDEF KİTLE: 0.
HOPARLÖR 1: 0.
Bu durumda Yani, biz Her zaman sure-- yapmak gerekir
yerine dönen boyutu eksi 1, çünkü biz
Bizim eleman olduğunu biliyoruz 1 daha az depolanmış olacak
Bizim boyutu ne olursa olsun, bu sadece ilgilenir.
Bu biraz daha zarif bir şekilde var.
Ve biz sadece bizim, azaltma Daha sonra boyutu ve boyutunu geri dönmek.
Mmhmm?
>> İZLEYİCİ: Ben, sadece genel olarak tahmin Neden bu veri yapısı olur
yararlı?
>> HOPARLÖR 1: Bu sizin bağlamda bağlıdır.
Teorinin bazı Yani, Eğer OK Şarkı söylemeyi kes çalışıyorsanız,
yararlı varsa bakayım dışarıdan daha faydalıdır
CS.
Yığınları ile, her zaman ihtiyacınız bir şey izlemek için bu
en son eklenen edildiğinde ise Bir yığın kullanmak istediğiniz gidiyoruz.
>> Ve ben iyi düşünemiyorum Şu anda bu örneği.
Ama ne zaman son şey, sizin için en önemli olan
Bu zaman bir yığın var yararlı olacak.
Ben eğer düşünmeye çalışıyorum Bu iyi bir tane var.
Gelecek iyi bir örnek düşünüyorsanız 20 dakika, ben kesinlikle size söyleyecektir.
>> Ama genel olarak, bir şey varsa, gibi çoğu nereye En son dedi
Bu, en önemli var olan burada bir yığın devreye giriyor.
Kuyruklar Oysa tersi türüdür.
Ve tüm küçük köpekler.
Doğru, bu harika değil mi?
Ben gerektiği gibi hissediyorum Sadece bir tavşan video var
Sağ ortasında Eğer çocuklar için bölüm
Bu, yoğun bir kesitidir için.
>> Yani bir kuyruk.
Temelde bir sıra, bir çizgi gibi.
Siz bu gün emin değilim kullanımı, Sadece bizim yemek salonlarında gibi.
Yani biz gitmek zorunda ve ben, bizim tepsileri olsun
emin satır beklemek zorunda tokatlamak veya yiyecek almak için.
Burada >> Yani fark Bu FIFO olmasıdır.
Böylece LIFO ilk olarak son olarak ise dışarı, FIFO ilk giren ilk çıkar, içinde.
Yani bu nereye koyduğunuzu ne olursa olsun İlk üzerindeki en önemli.
Eğer bekliyorlardı Yani eğer Bir line-- sizi can
Eğer gitti eğer hayal Yeni iPhone gidip
ve bir yığın nerede doğrultusunda son kişi, ilk aldım
insanlar birbirlerini öldürecek.
>> Yani FIFO, hepimiz çok tanıdık Burada gerçek dünyada beraber,
ve tüm aslında ile ilgisi yoktur tür bütün bu çizgi yeniden
ve yapısını kuyruk.
Yığını oysa Yani, Biz itme ve pop var.
Bir sıra ile, biz var enqueue ve dequeue.
Yani enqueue temelde anlamına gelir sırtına koymak,
ve dequeue araçlar almak Önden kapalı.
Yani bizim veri yapısı olan bir biraz daha karmaşık.
Biz takip etmek için ikinci bir şey var.
>> Kafa olmadan Yani, bu Doğru, tam bir yığın nedir?
Bu bir yığın aynı yapıdır.
Farklı olan tek şey artık biz ise Ne düşünüyorsunuz bu kafa var
izlemek için gidiyor?
>> İZLEYİCİ: Birincisi.
>> HOPARLÖR 1: Sağ, biz koymak ilk şey.
Bizim sıranın başkanı.
Kim doğrultusunda ilk var.
Pekala, bu yüzden Enqueue yaparsanız.
Yine, herhangi Bu veri yapıları,
Biz bir dizi ile uğraşıyoruz yana, biz boşluk olup olmadığını kontrol etmek gerekir.
>> Bu bana söylemek gibi bir tür olduğunu Siz, bir dosyayı açarsanız,
Eğer null kontrol etmek gerekir.
Bu yığınlar herhangi ve kuyruklar, ihtiyacınız
Biz çünkü boşluk olup olmadığını görmek için Bir sabit boyut dizi ile ilgili,
Hepimizin 5'e kadar ötürü-- 0, 1 gördüğünüz gibi.
Yani biz bu durumda ne çek biz hala boşluk olup olmadığını görmek için.
Bizim boyut kapasitesinin daha düşük mü?
>> Eğer öyleyse, biz de bunu saklamak gerekir bizim boyutunu güncellemek ve kuyruk.
Yani kuyruk bu durumda ne olabilir?
Bu açıkça yazılması değil.
Nasıl biz depolamak?
Kuyruk ne olurdu?
>> Yani bu örnek üzerinden yürüyelim.
Yani bu büyüklükte 6 bir dizi, değil mi?
Ve biz şu anda, bizim boyut 5'tir var.
Biz koymak ne zaman ve gidiyor Sağ beşinci endeksi, içine gitmek için?
Yani kuyruk saklayın.
>> Kuyruk yazmak için başka bir yolu sadece olur boyutu endeksi bizim dizi, doğru?
Bu boyut 5'tir.
Sonraki şey 5 içine gidecek.
Serin?
TAMAM MI.
Bu biraz daha karmaşık olur Biz kafa karıştırmasını başladığınızda.
Evet?
>> İZLEYİCİ: anlamına mı ki Bir dizi ilan olurdu
Beş element uzun ve o zaman biz bunun üzerine ekliyoruz?
>> HOPARLÖR 1: Hayır
Yani bu durumda, bu bir yığın.
Bu ilan edilecek büyüklüğü 6 bir dizi olarak.
Ve bu durumda biz Sadece bir boşluk sol var.
>> Tamam, bu yüzden bir şey bu olduğunu durumda, başımız 0, eğer,
o zaman biz sadece boyutunda ekleyebilirsiniz.
Ama biraz yanıltıcıdır alır Aslında, çünkü onlar
Bir slayt yok Bunun için, bu yüzden ben gidiyorum
öyle değil, çünkü birini çizmek için Oldukça basit senin kez
şeylerden kurtulmak başlar.
Bir yığın oysa Yani Eğer sadece hiç var
boyutu ne endişelenecek ne zaman bir şey ekliyoruz,
bir sıra ile de yapmak gerekir Başınızı hesaba emin,
Çünkü kuyruklar hakkında serin şey olduğunu Eğer kapasitede değilseniz,
aslında etrafında sarın yapabilirsiniz.
>> Tamam, bu yüzden bir şey-- oh, Bu korkunç tebeşir olduğunu.
Dikkate Bir şey böyledir.
Biz sadece beş yaparız.
Tamam, bu yüzden biz gidiyoruz kafa burada olduğunu söylüyorlar.
Bu, 0, 1, 2, 3, 4'tür.
>> Kafa var, ve Onlara bir şeyler var lütfen.
Ve biz doğru, bir şey eklemek ister misin?
Yani şey gerektiğini biliyorum kafa daima olmasıdır
Bu şekilde hareket edecek ve Daha sonra döngü yeniden etrafında, tamam mı?
>> Peki bu kuyruk doğru, alanı vardır?
Bu, başından boşluğu vardır Bu tersi tür.
Bu yüzden yapmamız gereken ne ise kuyruk hesaplamak gerekir.
Eğer biliyorsanız sizin Kafa taşındı değil, kuyruk
En sadece dizi boyutta dizini.
>> Ama gerçekte, bir kuyruk kullanıyorsanız, Başınızı muhtemelen güncellenmektedir.
Yani yapmanız gereken ne Aslında kuyruk hesaplamak.
Peki ne yapmak bu formül Burada, sana izin vereceğim hangi
adamlar düşünmek, ve o zaman bunun hakkında konuşacağım.
Yani bu kapasitesidir.
>> Yani bu aslında olacak bunu yapmak için bir yol vermek.
Çünkü bu durumda, ne?
Başımızı 1 de, bizim boyut 4 olduğunu.
Biz 5 ile o mod, biz 0 olsun, hangi nerede biz girmelisiniz olduğunu.
>> Öyleyse bir sonraki durumda, Bunu yapmak için olsaydı,
tamam, en sıradan çıkarma şey edelim diyorum.
Bu sıradan çıkarma.
Biz doğru, bu eleman çıkarmak?
>> Ve şimdi bizim baş burada işaret ediyor, ve biz başka bir şey eklemek istiyorum.
Bu temelde geri hattı, değil mi?
Kuyruklar dizi etrafında sarabilirsiniz.
Bu temel farklar biri.
Yığınlar, bunu yapamazsın.
>> Kuyruklar ile yapabilirsiniz tüm bu konularda çünkü
Bildiğiniz ne olduğunu en son eklenen edildi.
Her şey ilave olacak yana Bu sola doğru yönde, bu durumda,
ve sonra etrafında sarın yapabilirsiniz Yeni elemanlar koyarak devam
dizinin ön Gerçekten değil çünkü
Artık dizinin ön.
Siz başından düşünebilirsiniz Kafan aslında nerede olduğu dizi.
>> Peki bu formül nasıl Eğer kuyruk hesaplamak.
Bu mantıklı mı?
TAMAM MI.
Tamam, dequeue, ve sonra Siz 10 dakikanız var
Bana herhangi bir aydınlatıcı soru sormak Ben deli olduğunu biliyorum çünkü, istiyorum.
>> Pekala, aynı yol-- yüzden Siz fark olmadığını ben bilmiyorum
ama CS tüm desenleri hakkında.
Şeyler oldukça fazla olan Sadece küçük tweaks ile aynı.
Burada Yani aynı şey.
Biz eğer biz aslında görmek için kontrol etmeniz gerekir Sağ bizim kuyruğunda bir şey var?
Tamam, 0'dan bizim boyut büyüktür, Say?
Serin.
>> Biz yaparsak, o zaman bizim baş, hareket hangi Ben sadece burada gösterdi budur.
Biz bir daha olmasını başımızı güncelleyin.
Ve sonra eksiltme bizim boyut ve elemanının döner.
>> Çok daha somut var study.cs50.net kod,
ve ben çok gidiş tavsiye Eğer zamanınız varsa bunun üzerinden,
Hatta sadece bir pseudo-code eğer.
Ve siz konuşmak istiyorsanız Bana bir biri ile, bana bildirin lütfen bu
biliyorum.
Ben mutlu olurdum.
Veri yapıları, eğer Eğer CS 124 almak, size olacak
veri yapıları çok olsun biliyorum Eğlenceli ve bu sadece başlangıç.
>> Bu yüzden zor olduğunu biliyorum.
Tamam.
Biz mücadele.
Ben hala yapmak.
Yani bu konuda çok fazla endişelenmeyin.
>> Ama bu temelde, sizin olduğunu veri yapıları dersi çökmesine.
Ben çok biliyorum.
Bir şey var mı ki tekrar gitmek istersiniz?
Biz aracılığıyla konuşmak istediğiniz bir şey?
Evet?
>> İZLEYİCİ: Bu örnek için, bu yüzden Yeni kuyruk o aşkın, 0 altındadır?
HOPARLÖR 1: Evet.
HEDEF KİTLE: Tamam.
Öyleyse, geçiyor Eğer 1 artı 4 veya-- olurdu
>> HOPARLÖR 1: Yani diyordun, Biz gitmek istediğinizde tekrar yapmak?
HEDEF KİTLE: Evet.
Eğer bir konrtol bulmaktan Yani nerede Eğer ki gelen kuyruk hesaplanması?
>> HOPARLÖR 1: Yani kuyruk Ben bu değişti in-- oldu.
Yani burada bu örnekte, bu oldu tamam, bakıyoruz dizi?
Yani biz 1, 2, 3, ve 4 şeyler var.
Yani bizim kafa 1'e eşit olduğunu var Bu nokta, bizim boyut 4'e eşittir
Bu noktada, değil mi?
>> Tüm bu dava kabul?
Bu yüzden baş artı boyutu, hangi yapmak Bize 5 verir, ve sonra biz 5 ile mod.
Biz 0 olduğunu bize söyler, 0 olsun nerede boşluk var bizim kuyruk vardır.
>> İZLEYİCİ: Bir kap nedir?
>> HOPARLÖR 1: kapasitesi.
Özür dilerim.
Demek dizinin boyutu.
Evet?
>> İZLEYİCİ: [duyulamaz] önce Biz elemanı iade?
>> HOPARLÖR 1: Yani biz hareket baş veya anı iade?
Biz bir hareket Yani, boyutunu azaltma?
Tut.
Kesinlikle başka unuttum.
Boşver.
Başka bir formül yok.
Evet, sen dönmek istiyorum Baş ve sonra geri hareket ettirin.
>> İZLEYİCİ: Tamam, çünkü azından bu nokta, kafa, 0'dan oldu
ve sonra geri dönmek istiyorum endeks 0 ve sonra kafa 1 yapmak?
>> HOPARLÖR 1: Sağ.
Ben başka olduğunu düşünüyorum Böyle bir formül tür.
Ben üstüne kafamı o yok Sana yanlış bir vermek istemiyorum.
Ama mükemmel geçerli olduğunu düşünüyorum diyelim ki, tamam, bu element-- saklamak ne olursa olsun
başın eleman azaltma bu-- sizin boyut, başınızı üzerinde hareket ve dönüş
ne olursa olsun unsurdur.
Bu mükemmel geçerli değil.
TAMAM MI.
Bu değil gibi hissediyorum most-- gibi değilsin
Buradan yürüyerek gidiyor gibi, evet, ben çalışır biliyorum.
Ben hepsi var.
Bu iyi.
Söz veriyorum.
Ancak veri yapıları şey olduğunu o zaman bir sürü alışmak alır.
Zor Muhtemelen biri şeyler, ben ders, bence.
>> Yani kesinlikle alır tekrarlama ve at-- I seyir
Gerçekten bağlantılı listeler bilmiyordum Onlarla çok fazla yaptım kadar,
Aynı şekilde ben yaptım Gerçekten işaretçileri anlamak
Ben yaşadım kadar iki öğretmek için yıl ve onunla kendi psets yapmak.
Bu yineleme ve çok zaman alır.
Ve sonunda, bu tür tıklayın edecektir.
>> Ama bu arada, ne tür varsa Bir üst düzey anlayış ne
Bu onların artılarını, do ve ne olduğu cons--
biz gerçekten vurgulamak eğilimindedir, Özellikle intro ders.
Gibi, neden kullanmak istiyorsunuz Bir bir dizi üzerinde deneyin?
Gibi, pozitif nelerdir ve bunların her birinin negatif?
>> Ve Ticaret-off anlamak Bu yapıların her biri arasında
Şu anda çok daha önemli ne olduğunu.
Deli biri olabilir bu soru ya da iki
itme uygulamak için size soracağım veya pop veya Enqueue ve Dequeue uygulamak.
Ama çoğunlukla, bu sahip üst düzey anlayış ve daha fazla
sezgisel kavramak değildir aslında daha önemli
bunu uygulamak mümkün.
>> Bu gerçekten harika olurdu hepiniz eğer dışarı çıkmak ve bir deneyin uygulamak gidebiliriz,
ama biz mutlaka değil anlamak Şu anda en makul şey.
Ama isterseniz, sizin pset içinde yapabilirsiniz için, ve sonra uygulamayı alırsınız,
ve sonra belki olacak gerçekten anlıyorum.
Evet?
>> İZLEYİCİ: Tamam, olanlar hangi nedenle Biz pset kullanmak demek?
Ben onlardan birini kullanmak gerekir mi?
HOPARLÖR 1: Evet.
Yani seçim var.
Ben, biz bu durumda sanırım pset biraz bahsetmek
Ben bu koştu çünkü.
Senin pset Yani, sen, sizin var denemeden veya karma tablo seçimi.
Bazı insanlar çalışacağız ve, çiçeklenme filtreleri kullanın
ancak bu teknik olarak doğru değildir.
Çünkü onların olasılık doğası, bazen yanlış pozitif verir.
Onlar olsa, içine serin bir görünüm sensin.
Son derece seyir tavsiye Onlara en azından.
Ama senin seçim var Bir karma tablo ve deneyin arasındadır.
Ve bu nereye olacak Eğer sözlükte yükleyin.
>> Ve seçmeniz gerekir senin hash fonksiyonu,
kaç seçmek gerekir Eğer var kovalar, ve değişecektir.
Daha fazla kova varsa gibi, belki daha hızlı koşacağız.
Ama belki bir harcıyorsun uzayın çok olsa bu şekilde.
Bunu anlamaya var.
Mmhmm?
>> İZLEYİCİ: Bunu daha önce söylediğim diğer karma işlevlerini kullanabilirsiniz,
biz yok bir karma işlev oluşturmak?
>> HOPARLÖR 1: sağ Evet.
Yani tam anlamıyla karma işlevi için, google gibi "hash fonksiyonu"
ve biraz serin olanları arayın.
Sen inşa beklenmemektedir Kendi hash fonksiyonları.
İnsanlar harcamak onların Bu şeyler tezler.
>> Yani kendi bina hakkında endişelenmeyin.
Ile başlamak bir online bulun.
Bazıları var biraz manipüle
yaptığınızdan emin dönüş türleri maç ve etajer, başlangıçta bu yüzden,
Ben bir şey kullanarak tavsiye ederim gerçekten kolay ki belki sadece
ilk harfi sağlamalarının.
Ve sonra o çalışma var bir kere, bir soğutucu karma işlevi içeren.
Mmhmm?
>> İZLEYİCİ: Bir denemek istiyorum olabilir veya verimli ama, da-- sadece zor
>> HOPARLÖR 1: Yani deneyin, sanırım, uygulamak için sezgisel zordur
ama çok hızlı.
Ancak, daha fazla yer kaplar.
Yine, bu iki optimize edebilirsiniz Farklı yollar ve yollar vardır amaçlara yönelik
HEDEF KİTLE: Bunu nasıl derecelendirilir vardır?
O matter-- mu
>> HOPARLÖR 1: Yani kademeli konum normal yolu.
Sen tasarım üzerinde kademeli gidiyoruz.
Hangisini seçerseniz yapmak yolu, istediğiniz o olabilir o kadar zarif emin olun
ve verimli olması gibi.
Ama bir deneyin ya da karma seçerseniz masa, sürece çalışır gibi,
biz ile mutluyuz.
Eğer bir şey kullanmak Ve bu sağlamalarının ilk harfi, yani sorun yok
gibi belki tasarım-bilge gibi.
Biz de ulaşan ediyoruz Bu semester-- nokta
Bilmiyorum eğer sen eğer noticed-- adamlar
pset notları biraz düşüş Çünkü tasarım ve etajer,
Bu mükemmel para cezası.
Bir noktaya gidiyor nerede, sizin programlar daha karmaşık alıyorsanız.
Daha fazla yerler vardır Eğer üzerinde artırabilirsiniz.
>> Yani gayet normal.
Bu konum değil senin pset daha kötü yapıyor.
Bu sadece biz şimdi size zor davranıyorsun oluyor.
Yani herkes bunu hissediyor.
Ben sadece bütün psets kademeli.
Ben herkesin duygu biliyorum.
>> Peki bu konuda endişeli olmayın.
Ve hakkında herhangi bir sorunuz varsa önceki psets veya artırabilir yolları,
Ben denemek ve özel yorum yerler, ama bazen geç
ve ben yoruluyorum.
Başka şeyler var mı hakkında veri yapıları?
Ben sizler gerçekten yapmak eminim Artık onlar hakkında konuşmak istiyorum,
varsa ancak, ben mutluyum şey gibi, onların üzerinde gitmek
dersin bu geçmiş itibaren hafta veya geçen hafta.
>> Ben bu yüzden, geçen hafta tüm yorum olduğunu biliyorum bazı inceleme üzerinden atlanır olabilir
Dersin gelen.
Ben cevap verebilir Başka soru?
Tamam, tamam.
Peki, siz 15 dakika erken çıkmak.
>> Ben, bu en azından yarı-yardımcı oldu umuyoruz ve ben önümüzdeki hafta sizleri göreceksiniz,
veya Perşembe ofis saatleri.
Aperatifler için var istekleri vardır Gelecek hafta, bu şey?
Ben bugün şeker unuttum çünkü.
Ve ben son şeker getirdim hafta, ama, Columbus Günü
yani altı kişi var gibi kim kendilerine şeker dört torba vardı.
Ben starbursts getirebilir sizin gibi yine eğer.
Starbursts?
Tamam, iyi geliyor.
, Büyük bir gün adamlar var.